第9章 习题解答
如果G中任意一对结点和每一条边，有一条连接这两个结点而不含有这条边的基本路。G为具有至少三个结点的连通图。
设G中有一个桥e，则G-?e?为不连通图，令G1，G2为G-?e?中的两个不同连通分支，G1与G2非空，设u是G1中一个结点，v是G2中一个结点，在G中，因为图连通，故u到v的任一条路上均含有边e，与题设矛盾，所以中不可能有桥。
故(6)?(1)。
综上各点，(1)(2)(3)(4)(5)(6)(7)为等价命题。
9.试证明图的每一个结点和每一条边，都只包含于一个弱分图中。
证明：设结点u包含于两个不同的弱分图中，设这两个弱分图为G1=?V1,E1?和G2=?V2,E2?。则u?V1∩V2。
由于略去了方向后，V1中所有结点与u连通，V2中所有结点与u连通，故V1与V2中的所有结点相互连通，这与G1和G2是两个不同的弱分图矛盾。故任一结点不可能包含于两个不同的弱分图中。
如果一条边包含于两个不同的弱分图中，该边的两个端点也包含于两个不同的弱分图中，根据以上的证明，这是不可能的。因此，任一边也只包含于一个弱分图中。
10.试证明一个有向图G是单侧连通的当且仅当它有一条经过每一结点的路。
证明：设图中有一条经过每个结点的路，即任何结点都在此路上，则通过此路，一个结点到另一个结点可达，该图是单侧连通的。
设图是单侧连通的，证明图中有一条路经过图的每个结点。 对结点数目v进行归纳。
当v＝1，v＝2时，在单侧连通图中，显然有经过图的每个结点的路。
设v＝k时，有一条经过图的每个结点的路v1v2…vp，其中结点可能有重复，这条路上的结点的下标只表示该路所经过的结点的次序，显然，k≤p。例如在图9.84(a)给出的的路u1u2u3u4u5u2u3u6u7就有重复结点，故v1＝u1，v2＝u2，v3＝u3，v4＝u4，v5＝u5，v6＝u2，v7＝u3，v8＝u6，v9＝u7。
当v＝k＋1时，取一个结点u，在图G中删去u，使G－?u?还是单侧连通。根据归纳假设，G－?u?有一条经过每一个结点的路L：v1v2…vp。
令i=max?s| vS在路L上且vS到u有路?，j=min?s| vS在路L上且u到vS有路?。假如j＞i＋1，则必有t满足i＜t＜j。由于G是单侧连通的，vt与u之间有路。如果该路是从 vt到u，则与i=max?s| vS在路L上且vS到u有路?的定义矛盾。如果该路是从u到vt，则与j=min?s| vS在路L上且u到vS有路?的定义矛盾。故而j＞i＋1是不可能的，只可能是j≤i＋1。
当j＝i＋1时，有经过每一个结点的路v1v2…vi…u…vi+1vi+2… vp。如图9.84 (b)所示。 当j≤i时，有经过每一个结点的路v1v2…vj…vi…u…vj…vivi+1… vp。如图9.84 (c)所示。
11
第9章 习题解答
12
第9章 习题解答
习题 9.4
1.设G=?V,E?是一个简单有向图，V=?v1, v2, v3, v4?，邻接矩阵如下：
??0100?A(G)=?0011????1101?
??1100???⑴ 求v＋
1的出度deg(v1)。
⑵ 求vdeg－
4的入度(v4)。
⑶ 由v1到v4长度为2的路有几条？
解：⑴ deg＋
(v1)=1
⑵ deg－
(v4)=2 ??0100??100??011?⑶ A2= AA=?0011????0
?0011???0?2201???1101??211???1100???1101?=
??100????1?1???0111???由于a214=1，所以由v1到v4长为2的路有1条。 2.有向图G如图9.27所示。
⑴ 写出G的邻接矩阵。
⑵ 根据邻接矩阵求各结点的出度和入度。
⑶ 求G中长度为3的路的总数，其中有多少条回路。⑷ 求G的可达性矩阵。
⑸ 求G的完全关联矩阵。
⑹ 由完全关联矩阵求各结点的出度和入度。
??0110?解：⑴M=?1000???R?0101?
??0000???4?4⑵deg＋
(v－
1)=2，deg(v1)=1， deg＋(v)=1，deg－
2(v2)=2， deg＋(v－
3)=2，deg(v3)=1， deg＋(v－
4)=0，deg(v4)=1。
??1101??1110?⑶ A2=?0110?101????3?1??1000? ，A
=?0110?
??0000????4?4??0000???4?4长度为3的路有8条，其中回路3条。
13
第9章 习题解答
?3??2⑷ C3=A0+A1+A2+A3=?1??0?321??1??311??1 =P?1221????0001???4?4111??111?
111??001??
?1?1100?????110?10?⑸ G的完全关联矩阵?
00?111????0000?1???⑹deg(v1)=2，deg(v1)=1，deg(v2)=1，deg(v2)=2，deg(v3)=2，deg(v3)=1，deg(v4)=0，
－
deg(v4)=1。
3.无向图G如图9.28所示。 ⑴ 写出G的邻接矩阵。
⑵ 根据邻接矩阵求各结点的度数。
⑶ 求G中长度为3的路的总数，其中有多少条回路。 ⑷ 求G的连通矩阵。 ⑸ 求G的完全关联矩阵。
⑹ 由完全关联矩阵求各结点的度数。
?0??1
解：⑴邻接矩阵?
1??1?
111?
?
011?
100?
?
100??
＋－＋－＋－＋
⑵ deg(v1)=3，deg(v2)=3，deg(v3)=2，deg(v4)=2。 ?0??1⑶ A=?1??1?111??0
??
011?2?1
，A=?
100?1
??
?1100???111??011?100??100???3
??2?1??1?
111?
?
011?100?
?
100??
?0
??1?1??1?
111??3
??
011??2
=
100??1
???100???1
211?
?
311?
122?
?
122??
?0??1 A3=?1??1?211??4??311??5=
122??5???122???5555??455?
522??522??
长度为3的路的总条数66条，其中回路12条。
14
第9章 习题解答
?8??8
⑷ C4= A0+A1+A2+A3=?
7??7??1??1⑸ G的完全关联矩阵?0??0??1877???
877??1，G的连通矩阵为P=?1754???745??1?
?1100??0011?
0101??1010??111111111??1? ?1?1??⑹ deg(v1)=3，deg(v2)=3，deg(v3)=2，deg(v4)=2。
4.设G=?V,E?是一个简单有向图，V=?v1, v2,…, vn?， P=(pij)n×n是图G的可达性矩阵，
?)n×n是P的转置矩阵。易知， pij＝1表示vi到vj是可达的；pij?＝pji＝1表示vj到PT=(pij?＝1时，vi和vj是互相可达的。由此可求得图G的强分图。例如vi是可达的。因此pij∧pij图G的可达性矩阵P为：
?1??00P=???0??00100011111111111??1??1??01? PT=?1??1??1??1??10000??1??1000??01111? P∧PT=?0???01111???1111??00000??1000?0111?
?0111??0111?
其中：P∧PT定义为矩阵P和矩阵PT的对应元素的合取。
由此可知由?v1?，?v2?，?v3, v4, v5?导出的子图是G的强分图。 试用这种办法求图9.27的所有强分图。 ?1??1解：P=?1??0?111??1??111?T?1 ，∧PP=?111?1???0001???111??1??111??1∧
111??1???001???1110??1
??
110??1
=
110??1
???111???0
110?
?
110?
110?
?
001??
?v1,v2,v3?，?v4?导出的图是G的强分图。
5.设G=?V,E?是一个简单有向图，V=?v1, v2,…, vn?，A是G的邻接矩阵，G的距离矩阵D=(dij)n×n定义如下：
dij=∞ 如果d?vi,vj?=∞。 dii=0 i=1,…,n。
kdij=k k是使aij≠0的最小正整数。
试写出有向图图9.29的距离矩阵D。并说明dij=1是什么意义？
15