图论第一章课后习题解答-

1、 16. 在图 1-13 的赋权图中，找出 a 到所有其它顶点的距离。 v1 2 a 8 1 v3 v2 6 7 4 2 2 9 1 3 v4 9 v5 6 4 2 v6 b 图 1-13 解 1. A1= a，t(a = 0，T1 = 2. b1 = v3 3. m1 = 1, a2 = v3 , t(v3 = t(a + l(av3 = 1 (最小， T2 =av3 2. A2 =a, v3, b1 ( 2 ( 2 = v1 , b2 = v2 (1) 3. m2 = 1, a3 = v1 , t(v1 = t(a + l(av1 = 2 (最小， T3 =av3, av1 2. A3 =

2、a, v3, v1, b1 ( 3 ( 3 ( 3 = v 2 , b2 = v 2 , b3 = v4 3. m3 = 3, a4 = v4 , t(v4 = t(v1 + l(v1v4 = 3 (最小， T4 =av3, av1, v1v4 2. A4 = a, v3, v1, v4，b1(4 = v2，b2(4 = v2，b3(4 = v2, b4(4 = v5 3. m4 = 4, a5 = v5 , t(v5 = t(v4 + l(v4v5 = 6 (最小， T5 =av3, av1, v1v4, v4v5 2. A5 = a, v3, v1, v4, v5，b1(5 = v2，b2

3、(5 = v2，b3(5 = v2 , b4(5 = v2, b5(5 = v2 3. m5 = 4, t(v2 = t(v4 + l(v4v2 = 7 (最小， T6 =av3, av1, v1v4, v4v5, v4v2 2. A6 = a, v3, v1, v4, v5, v2, b2(6 = v6, b4(6 = b，b5(6 = v6，b6(6 = v6 3. m6 = 6, a7 = v6 , t(v6 = t(v2 + l(v2v6 = 9 (最小， T7 =av3, av1, v1v4, v4v5, v4v2, v2v6 2. A7 = a, v3, v1, v4, v5, v

4、2, v6, b4(7 = b，b5(7 =b，b7(7 =b 3. m7 = 7, a8 = b , t(b = t(v6 + l(v6b = 11 (最小， T8 =av3, av1, v1v4, v4v5, v4v2, v2v6, v6b 于是知 a 与 b 的距离 d(a, b = t(b = 11 由 T8 导出的树中 a 到 b 路 av1v4 v2 v6b 就是最短路。 17. 证明：若 G 不连通，则 G 连通。 证明 对 "u , v ÎV (G ,若 u 与 v 属于 G 的不同连通分支，显然 u 与 v 在 G 中连通；若 u 与 v 属于 g 的同一

5、连通分支，设 w 为 G 的另一个连通分支中的一个顶点，则 u 与 w，v 与 w 分别在 G 中连通，因此，u 与 v 在 G 中连通。 18. 证明：若 eE(G，则 (G(G-e(G+1。 证明 若 e 为 G 之割边，则 (G-e=(G+1，若 e 为 G 之非割边，则 (G-e=(G，所 以，若 eE(G，则 (G(G-e(G+1。 19. 证明：若 G 连通且 G 的每个顶点的度均为偶数，则对于任意的 vV(G，(G-v d(v/2 成立。 证明 设 C 为 (G-v的一连通分支，则在 G 中，v 有偶数条边伸向 C，若不然，C 中奇 度点个数为奇数。因此，v 至少有两条边伸向 C

6、，有 (G-vd(v/2 成立。 _ _ _ _ 20. 证明：若 G 的直径大于 3，则 G 的直径小于 3。 证明 "u , v ÎV (G ，若 uvÏE(G Þ uvÎE( G Þ d G - (u, v = 1 。若 uvÎE(G ，则 uvÏE( G 。分两种情况：(1 若在 V(G中任意顶点至少和 u,v 之一相连，在这种情况下， 对 G 中任意两个顶点 x,y，有 d G ( x, y £ 3 ，矛盾。 (2 V(G中存在一点 w,使得 uw,wvÏ E(G,则 uw,wv

7、06; E( G ，此时， d 以， G 的直径小于 3。 21设 G 是具有 m 条边的 n 阶简单图，证明：若 G 的直径为 2 且= n-2，则 m2n-4。 证明 在 G 中，设 d(v= = n-2,与 v 邻接的顶点设为：v1,v2,vn-2,剩下的一个顶点为 u, u 与 v 不能邻接。如下图所示。 由于 d(G=2，因此 u 与 v1,v2,vn-2 必邻接，否则，G u v 的直径大于 2。因此，该图中至少应该有的边数为 v n -2 n-2+n-2=2n-4,即：m2n-4。 v1 v2 v3 - G (u , v = 2 。所 22证明：若 G 是至少有三个点的简单连通图但不是完全图，则 G 有三个顶点 u, v 和 w，使得 uv, vwE，而 uw Ï E。 证明 G 是非完全图Þ $ u,