第7章-图论--3-4图的矩阵表示、欧拉图与汉密尔顿图

第9章图论7.3图的矩阵表示(MatrixNotationofGraph)•7.3.1简单图的邻接矩阵(AdjacencyMatrices)–有向图中的通路数与回路数•7.3.2图的可达矩阵(有向图)(ReachabilityMatrices)•7.3.3无环无向图的完全关联矩阵(CompleteIncidenceMatrices)•7.3.4简单有向图的完全关联矩阵(CompleteIncidenceMatrices)第9章图论7.3图的矩阵表示定义7.3.1设G=V,E是一个简单图，V=v1,v2,…,vnn阶方阵A(G)=(aij)n×n称为图G的邻接矩阵。简记为A。其中：i,j=1,…,n01jivvvvajijiij无边或到有边到　　7.3.1简单图的邻接矩阵（无向图、有向图）0111101011011010)(GA例如，右边无向简单图的邻接矩阵为：111212122212nnnnnnaaaaaaaaa即：A(G)=第9章图论例如，下边(a)、(b)两个有向简单图的邻接矩阵分别为：0001101111000010)(GA0010101100011100)(GA第9章图论简单图的邻接矩阵具有以下性质：①简单图的邻接矩阵中元素全是0或1。这样的矩阵叫布尔矩阵。简单图的邻接矩阵是布尔矩阵。②无向简单图的邻接矩阵是对称阵，有向简单图的邻接矩阵不一定是对称阵。③简单图邻接矩阵与结点在图中标定次序有关。例如上页图(a)的邻接矩阵是A(G)，若将图(a)中的接点v1和v2的标定次序调换，得到图(b)，图(b)的邻接矩阵是A′(G)。0010101100011100)(GA第9章图论考察A(G)和A′(G)发现，先将A(G)的第一行与第二行对调，再将第一列与第二列对调可得到A′(G)。称A′(G)与A(G)是置换等价的。一般地说，把n阶方阵A的某些行对调，再把相应的列做同样的对调，得到一个新的n阶方阵A′，则称A′与A是置换等价的。可以证明置换等价是n阶布尔方阵集合上的等价关系。虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。④对有向简单图来说，其邻接矩阵A(G)的第i行1的个数是vi的出度，第j列1的个数是vj的入度。⑤零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。第9章图论定理7.3.1设A(G)是图G的邻接矩阵，A(G)k=A(G).A(G)k-1，A(G)k的第i行，第j列元素等于从vi到vj长度为k的通路的条数。其中为vi到自身长度为k的回路数。推论设G=V,E是n阶简单有向图，A是有向图G的邻接矩阵，Bk=A＋A2＋…＋Ak，Bk=()n×n，则是G中由vi到vj长度小于等于k的路的条数。是G中长度小于等于k的路的总条数。是G中长度小于等于k的回路数。kijakiiakijbninjkijb11nikiib1kijb[注]：这里的矩阵乘法和矩阵加法都是按照正常的矩阵乘法和加法运算法则来计算。注意和第4章二元关系中的逻辑加区分开来。第9章图论【例7.3.1】设G=V,E为简单有向图，其图形如右下图所示，写出G的邻接矩阵A，算出A2，A3，A4且确定v1到v2有多少条长度为3的路?v1到v3有多少条长度为2的路?v2到自身长度为3和长度为4的回路各多少条?解：图G的邻接矩阵A如下：0100010000000100010100010A第9章图论利用矩阵的幂次定义，计算可得A2，A3，A4如下：2010000100010100101001010002000010000100010100000010000100010000100001000001AAA32010001010002000101000200020200010001010002000000010001000001000100000100010AAA43010000200020200101002020004000010000200020200000010000100010000100001000001AAA第9章图论=2，所以v1到v2长度为3的路有2条，它们分别是：v1v2v1v2和v1v2v3v2。=1，所以v1到v3长度为2的路有1条：v1v2v3。=0，v2到自身无长度为3的回路。=4，v2到自身有4条长度为4的回路，它们分别是：v2v1v2v1v2、v2v3v2v3v2、v2v3v2v1v2和v2v1v2v3v2。312a213a322a422a由A4还可得出判断：G中长为4的通路共有14条（即A4的全部元素的累加和等于14）,其中回路有10条（即A4的主对角线上所有元素的累加和等于10）类似地，由A3还可得出判断：G中长为3的通路共有10条（即A3的全部元素的累加和等于10）,其中回路有0条（即A3的主对角线上所有元素的累加和等于0）[说明]:在这里,通路和回路数是定义7.3.1意义下的。有些教材中邻接矩阵有其他的定义方式。第9章图论定义7.3.2设G=V,E是简单有向图，V=v1,v2,…,vnn阶方阵P(G)=(pij)n×n称为图G的可达性矩阵。简记为P。其中：pij=i,j=1,…,n[注]：1）在定义7.2.12中，规定了有向图的任何结点自己和自己可达。故简单有向图可达矩阵P(G)的主对角线元素全为1。2）有向图G强连通当且仅当P(G)的元素全为1.3）除了由该定义直接写出图G的可达矩阵之外，还可以采用下页所述方法计算图G可达矩阵：不可达到可达到　　jijivvvv017.3.2简单有向图的可达矩阵111212122212nnnnnnppppppppp即：P(G)=第9章图论方法一：设G=V,E是n阶简单有向图，V=v1,v2,…,vn，由可达性矩阵的定义知，当i≠j时，如果vi到vj有通路，则pij=1；如果vi到vj无通路，则pij=0；又由定理7.2.1知，如果vi到vj有通路，则必存在长度小于等于n–1的初级通路。依据定理7.3.1的推论，如下计算图G的可达性矩阵P：1）先计算Bn–1=A＋A2＋…＋An–1，2）设Bn–1=()n×n。若≠0，则令pij=1，若=0，则令pij=0，i,j=1,…,n。再令pii=1，i=1,…,n。就得到了图G的可达性矩阵P。令A0为n阶单位阵，则上述算法也可以改进为：1）计算Cn–1=A0＋Bn–1=A0＋A＋A2＋…＋An-1，2）设Cn–1=()n×n。若≠0，则令pij=1，若=0，则令pij=0，i,j=1,…,n。1nijb1nijb1nijb1nijc1nijc1nijc可达矩阵的两种计算方法：第9章图论例如：使用上述方法，计算【例7.3.1】中图G（如右下图所示）的可达性矩阵P。得，C4=310001300000433003730033411000110000011100111001112）则按上述方法规则可得，P=解：1）计算C4=A0＋A＋A2＋A3＋A4第9章图论方法二计算简单有向图G的可达性矩阵P，还可以用下述方法：设A是G的邻接矩阵，令A=(aij)n×n，A(k)=()n×n，A0为n阶单位阵。A(2)=A∘A，其中=(ai1∧a1j)∨(ai2∧a2j)∨…∨(ain∧anj)i,j=1,…,n。A(3)=A∘A(2)，其中(ai1∧)∨…∨(ain∧)i,j=1,…,n。……P=A0∨A∨A(2)∨A(3)∨…∨A(n–1)。其中，运算∨是矩阵对应元素的析取。[注]：这里运算中，注意加法是采用逻辑加。请大家自我阅读教材P292-293页例题2，了解并熟悉该方法。)(kija)2(ija)3(ija)2(1ja)2(nja第9章图论【例7.3.2】利用方法二求右图的可达性矩阵P。解:该图的邻接矩阵为0100001011001110A(2)010001000010001000101100110011000110111011101110A(1)(2)(3)(4)1110111011101110PAAAA(3)1100011011101110A(4)0110111011101110A故有：第9章图论定义7.3.3设G=V,E是简单无向图，V=v1,v2,…,vnn阶方阵P(G)=(pij)n×n称为G的连通矩阵。简记为P。其中：i,j=1,…,n[注]：无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。01不连通与连通与　jijiijvvvvp简单无向图的连通矩阵111212122212nnnnnnppppppppp即：P(G)=可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。第9章图论定义7.3.4设G=V,E是无环无向图，V=v1,v2,…,vp，E=e1,e2,…,eq，则p×q矩阵M(G)=(mij)p×q称为该无环无向图G的完全关联矩阵。简记为M。其中：i=1,…,p，j=1,…,q10ijijijvemve与关联　　与不关联7.3.3无环无向图的完全关联矩阵111212122212qqpppqmmmmmmmmm即：M(G)=例如，右边无环无向图的完全关联矩阵为：1000110000110111M(G)=第9章图论设G=V,E是无向图，G的完全关联矩阵M(G)有以下的性质：①每列元素之和均为2。这说明每条边关联两个结点。②每行元素之和是对应结点的度数。③所有元素之和是图各结点度数的和，也是边数的2倍。④两列相同，则对应的两个边是平行边。⑤某行元素全为零，则对应结点为孤立点。无环无向图完全关联矩阵的性质：对照上页实例以及右边无环无向图的完全关联矩阵可验证上述性质。11110001000100001011000010110100001M(G)=e1e2e3e4e5e6e7第9章图论补充说明：一般无向图的关联矩阵的定义如下：设G=V,E是一般无向图，V=v1,v2,…,vp，E=e1,e2,…,eq，记M(G)=(mij)p×q其中：i=1,…,p，j=1,…,q也称M(G)为一般无向图G的完全关联矩阵。也简记为M。例如，右边一般无向图的关联矩阵为：e1e2e3e4e5e6v5v1v2v3v4M(G)=2110000101110000110000000011002210ijijijijvemveve与关联次数为（即环的时候）与关联次数为1与不关联第9章图论定义7.3.5设G=V,E是简单有向图，V=v1,v2,…,vp，E=e1,e2,…,eq，则p×q矩阵M(