除用图形表示图外，还可用矩阵表示图，它的优点：(1)将图的问题变为数学计算问题，从而可借助计算机来研究图，进行相关的计算。(2)表示更清楚。知识点：1.邻接矩阵邻接矩阵求两点间不同长度的路的条数2.可达性矩阵3.完全关联矩阵由于矩阵的行和列有固定的次序，因此在用矩阵表示图时，先要将图的结点进行排序，若不具体说明排序，则默认为书写集合V时结点的顺序。预备知识预备知识图的邻接矩阵例例7-3.1(2)：写出下面有向图的邻接矩阵(1)邻接矩阵的主对角线元素aii=0。(2)主对角线以外的元素aijaij=1(i<>j)，说明图G是完全图；aij=0(i<>j)，说明图G是零图。(3)无向图的邻接矩阵是对称的；而有向图的邻接矩阵不一定对称；因为在无向图中一条无向边应看成方向相反的两条有向边，因此无向图的邻接矩阵关于主对角线对称。图的邻接矩阵的应用图G的邻接矩阵为图的邻接矩阵的应用3)证明l＝p＋1时定理成立。由故而aik是结点vi到vk长度为1的路的数目，是结点vk到vj长度为p的路的数目，所以上式右边的每一项表示从vi经过一条边到vk，再由vk经过一条长度为p的路到vj的总长度为p+1的路的数目，对所有k求和，是所有从vi到vj的长度为p+1的路的数目。所以对l=p+1成立。证毕。v4图G的邻接矩阵为若中至少有一个不为0，(3)判断G是否是连通图，及G中任意两个结点是否连通。在许多问题中需要判断有向图的一个结点vi到另一个结点vj是否存在路的问题。可达性矩阵表明了图中任意两个结点间是否至少存在一条路以及在任何结点上是否存在回路。定义7-3.2设简单有向图G=（V，E），其中V={v1，v2，…，vn}，n阶方阵P=（pij）nn，称为图G的可达性矩阵，其中第i行j列的元素设G是n阶简单有向图，由可达性矩阵的定义知，当i≠j时，如果vi到vj有路，则pij=1；如果vi到vj无路，则pij=0；又由定理7-2.1知，如果vi到vj有路，则必存在长度小于等于n–1的路。通过对图G的邻接矩阵A进行运算可得到G的可达性矩阵P。其方法如下：1．由A计算A2，A3，…，An。2．计算B=A+A2+…+An。3．将矩阵B中非零元素改为1，所得到的矩阵即为可达性矩阵P。由邻接矩阵A求可达性矩阵P的另一方法：将邻接矩阵A看作是布尔矩阵，矩阵的乘法运算和加法运算中，元素之间的加法与乘法采用布尔运算布尔乘：只有1∧1=1布尔加：只有0∨0=0计算过程：1．由A，计算A2，A3，…，An。2．计算P=A∨A2∨…∨AnP便是所要求的可达性矩阵。图的可达性矩阵的应用（2）利用可达性矩阵判断有向图的连通性利用可达性矩阵判断有向图的连通性利用可达性矩阵判断有向图的连通性（3）利用可达性矩阵P，求强分图例可达矩阵的应用可达矩阵的应用完全关联矩阵表示结点和边的关系无向图的完全关联矩阵有向图的完全关联矩阵定义7-3.3给定无向图G=<V,E>，V={v1,v2,……,vp}，E={e1,e2,……eq}，则矩阵M(G)=(mij)pq，其中110011111000001101000110000000(3)这个结果正是握手定理的内容，即各结点的度数之和等于边数的2倍。(4)一行中元素全为0，其对应结点是孤立结点。(5)若两列相同，则相应的两边平行。定义7-3.3给定简单有向图G=<V,E>，V={v1,v2,……,vp}，E={e1,e2,……,eq}，则矩阵M(G)=(mij)pq，其中v1V2V3V4v5（1）图中的一边关联两个点，M(G)中每列中只有一个1和一个-1。（2）每行中1的个数和-1的个数分别为相应结点的出度、入度。（3）结点vi的度数：（4）一行中元素全为0，其对应结点是孤立结点。小结7-4欧拉图和汉密尔顿图欧拉图与汉密尔顿图总结1.欧拉图七桥问题七桥问题的图表示一笔画欧拉图(Eulerian)欧拉图的判定例7-4.1无向图的欧拉路及欧拉回路的判断方法一笔画例7-4.3欧拉路（回路）判定定理7-4.1无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度数的结点。证明：设无向图G是连通的，且有零个或两个奇数度数的结点，则G具有一条欧拉路。方法：构造法证明-------思想：圈套圈(1)若有两个奇数度数结点，则从其中一个结点出发，开始构造一条边不同的路(即迹)。方法：从v0出发，经关联边e1进入v1，若deg(v1)为偶数，则必可由v1再关联边e2进入v2，如此下去，每边仅取一次，由于G连通，必可到达另一奇数度数结点停下来，得到一条迹L1。(2)若L1通过了G的所有边，则L1为欧拉路。(3)若G去掉L1(已通过的边)