离散习题(附答案) (9)(3)

第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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散习题(附答案) (9)(3)在线全文阅读。