第二章道路与回路 2.1道路与回路 定义2.1.1有问图G=(V,E)巾，若边序列P一(e,e2,…eg),其中e=(,),满 足：是cs:的终点，是e+1的始点，就称P是G的一条有向道路，如果eg的终点也是 e1的始点，则称P是G的·条有向回路。 如果P巾的边没有重复出现，则分别称为简单有向道路和简单有向回路。进而，如果 在P中结点也不重复出现，又分别称它们是初级有向道路和初级有向回路简称为路和回 路。显然，初级有向道路（回路）一定是简单有向道路（回路） 例2.⊥.1图2.1中，边序列(ce,e4,e,e)是有向道路，(es,e4,es,e,e3)是有向回路。 (e:,e,e1,ez)是简单有向道路，(es,e4e1,e2,e,)是简单有向回路。(e1,ea)是初级有向道路， (e1,e2ea)是初级有向回路。 定义2.1.2无向图G=(V,E)中，若边序列P=(e1,,…,e,),其中e=(:v),满 足，是e-,的一个端点，0，是eA1的一个端点，则称P是G中的一条链，或道路。如果e 与e1亦相接，称P是G中的一个圈，或回路。 如果P中没有重复出现的边，称之为简单道路或简单回路，若其中结点也不重复，又 称之为初级道路或初级回路。 图2.1 图2.2 例2.1.2图2.2中边序列(e4,es,e4,e6)是道路，(e,e5,e4,e6,eg)是回路：(e4,es,e1, ez)是简单道路，(e,ee1,e2,e)是简单回路；(e1,ez)是初级道路，(e1,eze)是初级回路。 例2.1.3设C是简单图G中含结点数大于3的一个初级回路，如果结点，和v,在 C中不相邻，而边(，x)∈E(G),则称(，v,)是C的一条弦。若对每一个∈V(G),都有 d(v)≥3，则G巾必含带弦的回路。 证明：在G中构造一条极长的初级道路P=(e,%2,…,e),不妨设e1=(vo),e= (-1)。由于P是极长的初级道路，所以和，的邻接点都在该道路P上。由已知条 件，d()≥3，不妨设T(vu）={1,a…},其中1<j<k,这时(o1,…,vv)是一条 初级回路，而(，)就是该可路中的一条弦。 ·11
例.2.1.4设G=(V,上)是无向图，如果V(G)可以划分为子集X和Y,使得对所有 的e一(u,)∈E(G),u和0都分属于X或Y,则称(G是二分图。证明：如果二分图G中存 在回路，则它们都是由偶数条边组成的。 证明：设C是二分图G的任一回路，不妨设∈X是C的始点，由于(？是一分图，所 以沿回路C必须经过偶数条边才能达到某结点出∈X,因而只有经过偶数边才能回到。 定义2.1.3设G是尤向图，若G的任意两结点之问都存在道路，就称G是连通图， 否则称为非连通图。 如果G是有向图，不考虑其边的方向，即视之为无向图，若它是连通的，则称G是连 通图。 在非连通图G中，其极大的连通子图称为连通支。显然G的每个连通支都是它的导 出子图。 例2.1.5图2.1和2.2都是连通图，图2.3是非连通图。其中(a)有两个连通支，它 们的结点集分别是{y,2,}和{4，}，(b)有三个连通支，其结点集是{1,2,3}，{4， v}和{v6}。 1● (a) (b) 图之.3 图2.4 例2.1.6图2.4是连通图，它不含回路，而且在任意两结点之间都只有唯一的一条 初级道路。这种图称为树，它是含边数最少的连通图。 例2.1.7设G是简单图，证明当m>号(n-1)(-2)时，G是连通图。 证明：假定G是非连通图，则至少含有2个连通支设分别为G,一(V1,E),(Ga=(V2, E:>。其中V:()=1,|V2(G2)|=2。n,十n2=n。由于G是简单图，因此 E,(G,1≤高4，m-1D, 1 E,(G)川≤2：n:-1), m≤合4m,-1)+::-1). 由于n1≤n一1，n2≤一1， 所以 m≤分m-1Da-1+%-1) =2m-10-2. ·12·
与心3知条件矛盾，故G是连通图。 2.2道路与回路的判定 通常可以利用邻接矩阵或搜索法判定某个图G的两结点间是否存在道路，或者判定 它是否连通。首先介绍邻接矩阵的判定方法。 设A=(ai)mx是G的邻接矩阵。由A的定义，a,=1長示(，v,)∈E(C),即，可以 通过某条边e到达，或老说G中有道路从，到：，根据矩阵乘法，设A2一()，有 a u,十0当旦仪当存在太，使山6=u=1。也就是说，如米(G中行在结点，满足(，)， ()∈E(G),即经过2条边().(4，ei）,,可以到达，时，a≠0。同理，A(l≤n) 中的元素a出≠0表示了可以经过（条边到达，因此令 P-:A+A2+…÷A“, 如果，=t,说明，有t条道路可以到达y,若p,=0,即n步之内不能到达v,则在( 中不存在，到℃，的路，否则，若，经过(>)步可达y,由抽屉原理，该道路上一定有在 重复出现的结点，而w之间的这段路C是一个同路，删去这段回路仍然可达；。由 于G中只存在n个不同的结点，所以只要：有道路到，一定有，≠0。 在许多实际问题中，往往只要求了解西与，之间是否存在道路。对此可以采用逻辑 运算的方法，即 ag-V(a￥DAa).l=2,3,…,n。 相应地 P=AVA2V…VA" 就是图G的道路矩阵。 用.上述方法求G的道路知阵，计算复杂性为O(n)。以下介绍的Warshall算法是一 个更好的方法，其计算复杂性是O()。 Warshall算法 begin 1.P←A, 2.for i=l to n do 3.for j-1 to n do 4, for k=1 to n do P+PkV(PAp)。 end. 例2.2.1采用Warshall算法计算图2.5道路矩阵的过程是： ·13·
0110 07 0 0 11 0 0 0 01 00000 10010 6 1100, ) 0111 00110 0 0 上1 0 P(i=1)=00001 P(i2)= 00001 00000 00000 11110 1 1110 0 11111 00111 P(=3)=00001 P(i=4)-P(i=3), 0000 0 1111 1 0 11117 11111 P(=5)=11111 00000 11111 图2.5 矩阵P中的粗体字表示该元素的值在本次循环中发生改变。 定理2.2.1 Warshall算法的结果是图G的道路矩阵。 证明：该定理的严格证明需要对三层循环分别使用归纳法。现只证其最外层循环。 基始：当=1时， pg'=pV(pHAp1t),k=1,2,…,n;j=1,2,…,n。 =1当且仅当pa=1或pn=p1=1,其中p0=1表明直接可达，pn=p1-1表明 ,可以经过v1到达。因此=1当且仅当结点集{，w}之间有v,到vw的路。 i=2时，=gV('A),夷=1,2，…，n:j=1,2,…,n。=1当且仅当g =1或君=p=1,其中'=1表明结点集(v,1,》之间有，到的道路；8和 p为1表明{，，2，t}之间v,有必通过v到达4的道路，因此，=1当且仅当结 点集{U,1,2,}中有到的道路。 设i=n一1时，-D=1当且仅当结点集{，，a,…,w,1,}之中有，到4的 道路。 则i=n时，=p》V(%”Ap), k=1,2,…n,j=1,2,…,n。 由归纳假设，-”表明结点集{，1…，0。-1}中有；到vs的路，p8-》=””=1,表 明结点集{口，v,…,-1,4}巾y,有通过v到达的道路。因此，p=1即是结点集 {v,1,…,心}之中有；到℃的道路。 ·14·
采用搜索的方法判断G中某一结点到另一结点v,是否存在道路经常更加方便。 常用的搜索法有广探法(Breadth First Search)和深探法(Depth First Search)。 广探法(BFS)是从(G的任一结点o开始，找它的直接后继集T+(0o),记为A1,然后 对A:中的每一结点分别找它们的直接后继集，这些直接后继集的并记为A:。依此类推， 直至达到目的。为了避免结点的重复搜索，可以首先对全部结点都给一个标记“0”，当， 被搜索到时，如果其标记为0，则，进入直接后继集，同时标记改为1，否则由于：已被搜 索因此不再进入直接后继集。 例2.2.2用BFS方法找图2.6中，到4的-·条道路。 解：如果采用正向表的输入结构，则有 135691113 263611363435 图2.6 ,-(v,)={2,s}, ∴.A1={v2,v6}e .+(02)={3,s}, -(6)={3,} ∴.A2={3,vs}。 下+()={1}， -(v5)={v3,,}, .A3={w4}。 因此G中存在1到4的道路。 从上例中可知，用BFS方法求两点间道路的计算复杂性是O(m)。 搜索结点： 含 钱元素： 01 1 图2.7 深探法(DFS)的特点与BFS截然不同。它从某一结点开始，只查找a的某个直接 后继，记下o1的父亲，然后再找，的某个未搜索过的直接后继2。依此类推。当从某 个结点，无法再向下搜索时，退回到它的父亲，1，然后再找，-的另一个未查过的直接 后继。形象地说，DFS的特点是尽量向下搜索，只有碰壁才回头。 采用栈结构以及前述的标记结点的方法可以完成DFS的搜索过程。 15