离散数学及其应用图论部分课后习题答案

1、作业答案：图论部分P165:习题九1、给定下面4个图(前两个为无向图，后两个为有向图)的集合表示，画出它们的图形表示。(1) Gi =<Vi,Ei>, Vi =Vi,V2,V3,V4,V5 , El =(Vl,V2),(V2,V3),(V3,V4),(V3,V3),(V4,V5) G2 =<V2,E2 >, V2 =M , Ei =(Vl,V2),(V2,V3),(V3,V4),(V4,V5),(V5,Vl)(3) Di =< V3 , E3 >,V3 = V1, E3 = < vi, v2 >, < v2, v3 A,父 v3, V2 &

2、gt;, < v4, V5 A, < v5, vi >(4) D2 =<V4,E4>Na =Vi, E3 =<,v2 >,<v2,v5 >,<v5,v2 >, < v3,v4 >, < v4,v3 >解答：(i)(2)I0、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样的图。(I) 5, 5, 3, 2, 2; (2) 3, 3, 3, 3, 2; (3) I, 2, 3, 4, 5; (4) 4, 4, 4, 4, 4解答：(I) (3)不存在，因为有奇数个奇度顶点14、设G是n(n之2)阶无向

3、简单图，G是它的补图，已知A(G) = k1，6(G) = k2,求4(G), 6(G)。解答：A(G)=n1k2； 6(G)=n_1_k1。15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。解答：(c)不是同构，从点度既可以看出，一个点度序列为3, 3, 1(d)同构，同构函数为4, 3, 3, 3, 3而另外一个为4, 4,2 f(x) =<34516、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。解答：(1)三条边一共提供 6度；所以点度序列可能是3, 3,0,0,0,0;3, 2, 1, 0, 0, 0;3, 1, 1, 1, 0, 0;2,2,2

4、, 0, 0,0;2, 2,1,1,0,0; 2, 1, 1, 1, 1, 0; 1, 1, 1, 1, 1, 1;由于是简单图，两种情形不可能图形如下：3, 3, 0;3, 2, 1;2, 2, 221、在图9.20中，下述顶点序列是否构成通路？哪些是简单通路？哪些是初级通路？哪些是回路？哪些是简单回路？哪些是初级回路?(1) a,b,c,d,b,e； (2) a,b,e,d,b,a； (3) a,d,c,e,b； (4) d,b,a,c,e;(5) a,b,c,d,e,b,d,c ； (6) a,d,b,e,c,b,d ； (7) c,d,a,b,c； (8) a,b,c,e,b解答：(1

5、)构成通路，且为初级通路，因为点不重复(2)构成了回路，但是不为简单回路和初级回路，因为有重复的边(a,b)(3)构成了初级通路，因为点不重复；(4)不构成通路，因为边 (a,c)不存在；(5)构成通路，但是不为简单通路和初级通路，因为有重复的边(d,c)(6)构成了回路，但是不为简单回路和初级回路，因为有重复的边(d,b)(7)构成了初级通路；(8)简单通路，但是不为初级通路，有重复边。23、用Dijkstra标号法求图9.22中各图从顶点v1到其余各点的最短路径和距离。解答步骤ViVVVV5V6V7V1*(Vi，0)(Vi,6)*(Vi,3)(V1产)(M产)(V1.00)(V1.00)(

6、V1产)2(M,6)一 *W,5)&,8)(V1.00)(V3,11)(V1产)3*(Vi,6)(V4,6)(V1.00)(V3.11)(V4.11)4*(V4,6)(V2,12)(V3,11)(V4,11)5(V2,12).* (V5.7)(V4.11)6(V2,12)*(V7,10)7*(V2,12)V1到丫2最短路为V1 t v2 ,路长为6;必到V3最短路为 T V3 ,路长为3；V1到丫4最短路为V1 T v3T v4 ,路长为5;Vi到V5最短路为 Vi T V3 T V4 T V5 ,路长为 6 ；Vl到V6最短路为 T % T V6 ,路长为12；Vi到V7最短路为Vi

7、 T % T V4 T V5 T V7 ,路长为7；Vi到V8最短路为 T / T V4 T V5 T V7 T Vg ,路长为10； (2)略。25、图9.23中各图有几个连通分支？给出它们所有的连通分支。解答:(a)有两个连通分支：aec和bdf ;(b)有三个连通分支：abd、c和ef ；(c)连通图，只有一个连通分支；(d)两个连通分支：afbgd和ech。38、写出图9.27的关联矩阵。-1110解答：000010-1000-1110-1000-110000000000-11-11-11040、写出图9.29中各图的邻接矩阵。解答:01(a)-00100 00 0110100(b)

8、0 00 01101000 10 1041、设有向图D =<V,E >,其中V =m，V2，V3，V4,其邻接矩阵为0101-01试求出D中各顶点的入度和出度。解答：出度：v13v21v31v4 ： 2;入度：v1 : 0;v2: 2;v3:3; V4 : 2;43、有向图 D如图9.29 (a)所示(1) D中v1道v4长度为1, 2, 3, 4的通路各有几条？(2) D中道v1长度为1, 2, 3, 4的通路各有几条？(3) D中长度为4的通路有多少条？其中长为4的回路有多少条?(4) D中长度小于或者等于 4的通路有多少条？其中多少条为回路?(5)写出D的可达矩阵。解答:M4

9、(1)(2)(3)(4)(5)一2中V1道V4长度为中道v长度为0101, 21, 2的通路各有4的通路各有中长度为4的通路有44条；其中长为4中长度小于或者等于4写出D的可达矩阵为-1M3的回路有2条;5条;11条.的通路有88条；其中22条为回路。11121 0P181:习题十1、图10.14中的哪些图是树?解答：（a）是树；（b）不是树，因为不连通。3、无向树T有8片树叶，2个3度分支点，其余分支点都是4度顶点，问T有几个4度分支点？请画出3棵非同构的这种无向树。解答：设有x个4度分支点，则T共有8+2+x=10+x个顶点。那么有9 + x条边。由握 手定理有 2（9 x） =8 2 3

10、 4x= 18 2x=14 4x= x = 2所以有2个4度分支点。4、无向树T有小。=2,3，,k)个i度分支点，其余顶点都为树叶，问T有几片树叶？kk解答：设有x片树叶，共有x+£ ni个顶点，那么有x+£ ni-1条边， i =2i /kkk而共有x+£ini度，由握手定理可知 x+£ ini=2(x1+£ ni) i =2i =2i =2k所以有 x =2 +£ (i -2)ni。 i -215、已知n阶m条边的无向图 G是k(k *2)棵树组成的森林。证明： m=n -k。 证明：方法一：对变量k进行归纳当k =1是，因为是

11、一棵树，显然成立；假设n阶m条边的无向图G是k-1棵树组成的森林，有 m = n-(k-1)；那么对于n阶m条边的无向图G是k棵树组成的森林，在任意两棵树中分别找一点进行连 一条边，那么得到的图则为n阶m+1条边的无向图G是k -1棵树组成的森林，那么 m +1 =n (k -1),所以 m = n - k。方法二：设k棵树中，分别有 ni个顶点和m条边，i =1,2,.,k,则有 kkm=Emi, n=2ni,5=八一1,即可得证。19、求图10.17中两个带权图的最小生成树。/ X ¥ 4 7 V>8/4、1110/7 14 39A /4 X /9(a)解答:P204:习题

12、叶1、判断图11.22中哪些是欧拉图？哪些是半欧拉图？对欧拉图给出一条欧拉回路。对半欧 拉图给出一条欧拉通路。对不是的，说明不是欧拉图或半欧拉图的理由。解答：（a）为欧拉图，全为偶度顶点；（b）为半欧拉图，1, 2两个顶点点度为3,其它为偶2、判断图11.23中哪些是欧拉图？哪些是半欧拉图？对欧拉图给出一条欧拉回路。对半欧 拉图给出一条欧拉通路。对不是的，说明不是欧拉图或半欧拉图的理由。bc点的入度s。解答：(a)为半欧拉图，a,c两点的出度和入度都相等；b点的入度比出度大1;比出度小1.(b)为欧拉图，每个顶点的入度和出度都相等。3、判断命题的真假。(1)完全图Kn是欧拉图。(2) n(n 2 2)阶有向完全图是欧拉图。(3)当r,s为正偶数时，完全二部分图Kr,s是欧拉图。解答：(1)为假，因为当n为偶数时，每个点的点度都为奇数。(2)真；有向完全图的出度和入度必然相等。(3)真，完全二部分图 Kr,s中，一部分点的点度全为r,另外一部分点的点度全为 10.说明图11.25中各图不是哈密顿图，也不半哈密顿图的理由。(b)解答：(a)删掉画圈的3个顶点，还剩下5个连通分支;(b)删掉画圈的4个顶点，还剩下 6个连通分支。由定理11.2和11.3可知不是哈密顿图，也不半哈密顿图。11、设G是无向连通图，证明：若 G中有桥或者割点