14.3图的连通性和14.4图的矩阵表示

114.2通路、回路通路与回路是图论中两个重要而又基本的概念本节所述定义一般说来既适合无向图，也适合有向图，否则将加以说明或分开定义。2定义14.11（通路、回路）给定图G，设G中顶点和边的交替序列Г=v0e1v1e2…vi-1eivi…envn若Г满足：对于i=1,2,…n，vi-1和vi是ei的端点（在G是有向图时，要求vi-1是ei的始点，vi是ei的终点），则称Г为从v0到vn的一条通路或链（chain）。v0和vn分别称为此通路的起点和终点。Г中边的数目n称为通路的长度(length)当v0=vn时，此通路称为回路（circuit）说明（1）可以用边的序列Г=e1e2…en表示通路或回路（2）在简单图中，可以只用顶点Г=v0v1…vn表示通路或回路3有边重复出现的通路称为复杂通路；有边重复出现的回路称为复杂回路。若通路中无边重复，则称该通路为简单通路；无边重复的回路称为简单回路。若通路中无边重复且无顶点重复，则称该通路为初级通路或路径（path）；无边重复且无顶点重复的回路称为初级回路或圈（cycle）。将长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈。易见（1）初级通路(回路)是简单通路(回路)，但反之不真。（2）通路、回路是图的子图。4注意（1）在无向图中，环和平行边构成的回路分别是长度为1和2的初级回路（圈）。（2）在有向图中，环和两条方向相反边（对称边）构成的回路分别是长度为1和2的初级回路（圈）。思考：在简单无(有)向图中，圈的长度至少为多长？在简单无向图中，圈的长度至少为3在简单有向图中，圈的长度至少为25通路、回路的性质定理14.5在一个n阶图中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n-1的通路。推论在一个n阶图中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n-1的初级通路。定理14.6在一个n阶图中，若存在vi到自身的回路，则从vi到自身存在长度小于等于n的回路。推论在一个n阶图中，若存在vi到自身的简单回路，则从vi到自身存在长度小于等于n的初级回路。614.3图的连通性7首先讨论无向图的连通性。定义14.12（连通）在一个无向图G=V，E中，如果顶点u，v之间存在通路，则称u，v是连通的（connected），记作uv。vV，规定vv。由连通的定义可以定义如下的无向图中顶点之间的连通关系:={u,v|u,vV∧u与v之间有通路}显然是自反的、对称的、传递的，所以是V上的等价关系。8定义14.13（无向连通图）若无向图G是平凡图或G中的任何两个顶点都是连通的，则称G是连通图（connectedgraph），否则称G为非连通图或分离图（disconnectedgraph）。例：完全图Kn（n1）为连通图，零图Nn（n2）都是分离图。9定义14.14（连通分支）设无向图G=V，E，V关于顶点之间的连通关系的商集V/={V1,V2,…,Vk}，Vi为等价类，称Vi的导出子图G[Vi]（i=1,2,…,k）为G的连通分支（connectedcomponent），连通分支数k常记为p(G)。或若无向图G由若干彼此不连通的子图组成，而每个子图是连通的，称这些子图为G的连通分支。显然若G为连通图，则p(G)=1；若G为非连通图，则p(G)2；Nn（n2）的连通分支为p(G)=n10思考题（1）n阶非连通的简单图的边数最多有多少条？最少呢？P289/P292-6(2)（2）证明：若无向图G中恰有两个奇度顶点，这两个奇度顶点必然连通。P291/P293-3911下面讨论有向图的连通性定义14.20在一个有向图D=V，E中，如果顶点u，v之间存在通路，则称u可达v，记作u→v。规定任意的顶点总是可达自身的，即uV，u→u。若u→v且v→u，则称u与v是相互可达的，记作uv，规定uu。12有向图有三种不同类型的连通图定义14.22（弱、单向、强连通图）在一个有向图D中，如果D的基图是连通图，则称D是弱连通图(weaklyconnectedgraph)。如果对于任意的两个顶点u，v，u→v与v→u至少成立其一，则称D是单向连通图（unilateralconnectedgraph）。如果对于任意的两个顶点u，v，均有uv，则称D是强连通图（stronglyconnectedgraph）。说明：强连通图一定是单向连通图，单向连通图一定是弱连通图。13强连通图和单向连通图的判别定理定理14.8有向图D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。定理14.9有向图D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。14例（1）（2）（3）（1）是强连通图（2）是单向连通图（3）是弱连通图1514.4图的矩阵表示16图的表示（1）集合定义（2）图形表示（3）矩阵表示目的（1）便于用代数知识来研究图的性质（2）便于用计算机来对图进行处理本节学习（1）图的关联矩阵(无向图和有向图)（2）有向图的邻接矩阵（3）有向图的可达矩阵17定义14.24（无向图的关联矩阵）设无向图G=V，E，V={v1,v2,…,vn}，E={e1,e2,…,em}，令mij为顶点vi与边ej的关联次数，则称(mij)n×m为G的关联矩阵，记为M(G)。易见，矩阵的第i行为顶点vi分别与边e1,e2,…,em的关联次数。矩阵的第j列为边ej分别与顶点v1,v2,…,vn的关联次数。关联两次与，关联一次与不相关联与jijijiijev2ev,1ev,0m对于mij显然有18例如：求下图的关联矩阵关联矩阵为：10000110000011001112)G(M19无向图关联矩阵的性质：n1iij)m,,2,1j(2m1）（m1jiij)n,,2,1i)(v(dm2）（m2)v(dmm3n1iim1jn1iijn1im1jij）（m1jij0m)5(即关联矩阵中每条边关联两个顶点（环关联的顶点重合）即关联矩阵中第i行元素之和为顶点vi的度数。即握手定理：各顶点的度数之和等于边数的2倍。(4)第j列与第k列相同，当且仅当边ej与ek是平行边。当且仅当vi是孤立点。1000011000001100111220定义14.25（有向图的关联矩阵）设有向图D=V，E中无环，V={v1,v2,…,vn}，E={e1,e2,…,em}，令的终点为，不关联与的始点为jijijiijev1ev,0ev,1m则称(mij)n×m为D的关联矩阵，记为M(D)。21例如：下图的关联矩阵为关联矩阵为：11100110000011100011)D(M22有向图关联矩阵的性质：23有向图关联矩阵的性质：（1），从而，这说明有向图关联矩阵中所有元素之和为0。n1iij)m,,2,1j(0mm1jn1iij0m1110011000001110001124有向图关联矩阵的性质：（1），从而，这说明有向图关联矩阵中所有元素之和为0。（2）有向图关联矩阵中，-1的个数、1的个数、边数m相等。这正是有向图握手定理的内容。n1iij)m,,2,1j(0mm1jn1iij0m1110011000001110001125有向图关联矩阵的性质：（1），从而，这说明有向图关联矩阵中所有元素之和为0。（2）有向图关联矩阵中，-1的个数、1的个数、边数m相等。这正是有向图握手定理的内容。（3）在有向图关联矩阵第i行中，1的个数等于d+(vi)，-1的个数等于d-(vi)。n1iij)m,,2,1j(0mm1jn1iij0m1110011000001110001126有向图关联矩阵的性质：（1），从而，这说明有向图关联矩阵中所有元素之和为0。（2）有向图关联矩阵中，-1的个数、1的个数、边数m相等。这正是有向图握手定理的内容。（3）在有向图关联矩阵第i行中，1的个数等于d+(vi)，-1的个数等于d-(vi)。（4）平行边所对应的列相同。n1iij)m,,2,1j(0mm1jn1iij0m1110011000001110001127定义14.26（有向图邻接矩阵）设有向图D=V，E，V={v1,v2,…,vn}，令aij(1)为顶点vi邻接到顶点vj边的条数，称(aij(1))n×n为D的邻接矩阵，记作A(D)，简记为A。1100100001000120)D(A例如：下图的邻接矩阵为28有向图邻接矩阵的性质：(1)，于是n1ji)1(ij)n,,2,1i)(v(dam)v(dan1iin1in1j)1(ij110010000100012029有向图邻接矩阵的性质：(1)，于是(2)，于是n1ji)1(ij)n,,2,1i)(v(dam)v(dan1iin1in1j)1(ijn1ij)1(ij)n,,2,1j)(v(dam)v(dan1jjn1jn1i)1(ij110010000100012030有向图邻接矩阵的性质：(1)，于是(2)，于是(3)所有元素之和为D中边的总数，也可看成D中长度为1的通路的总数。n1ji)1(ij)n,,2,1i)(v(dam)v(dan1iin1in1j)1(ijn1ij)1(ij)n,,2,1j)(v(dam)v(dan1jjn1jn1i)1(ijn1in1j)1(ija110010000100012031有向图邻接矩阵的性质：(1)，于是(2)，于是(3)所有元素之和为D中边的总数，也可看成D中长度为1的通路的总数。而为D中环的个数，即D中长度为1的回路总数。n1ji)1(ij)n,,2,1i)(v(dam)v(dan1iin1in1j)1(ijn1ij)1(ij)n,,2,1j)(v(dam)v(dan1jjn1jn1i)1(ijn1in1j)1(ijan1i)1(iia110010000100012032问下图中有多少条长度为2、3、4….的通路？33A0210001000010011'A0021000100110012A2=?A2=A’34利用有向图邻接矩阵计算D中长度为d(d1)的通路数和回路数。对于d=2,3,…，定义Ad=Ad(D)=(aij(d))n×n，其中()()()1dddijikkjkaaad个这样()()()dAADADAD在Ad中aij(d)为顶点vi到顶点vj长度为d的通路数aii(d)为顶点vi到自身的长度为d的回路数()nndijija11为D中长度为d的通路总数1()ndiiia为D中始于各顶点的长度为d的回路总数35定理14.11设A为有向图D的邻接矩阵，则Ad（d1）中元素为aij(d)为顶点vi到顶点vj长度为d的通路数，()nndijija11为D中长度为d的通路总数，()ndiiia1为D中长度为d的回路总数。推论设Bd=A+A2+…+Ad（d1），则Bd中元素bij(d)为D中顶点vi到顶点vj长度小于等于d的通路数，()nndijijb11为D中长度小于等于d的通路总数，()ndiiib1为D中长度小于等于