2023年7月19日发(作者：)

作业答案：图论部分

P165:习题九

1、 给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表示。

（1）G1V1,E1，V1{v1,v2,v3,v4,v5}，E1{(v1,v2),(v2,v3),(v3,v4),(v3,v3),(v4,v5)}

（2）G2V2,E2，V2V1，E1{(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)}

（3）D1V3,E3,V3V1,E3{v1,v2,v2,v3,v3,v2,v4,v5,v5,v1}

（4）D2V4,E4,V4V1,E3{v1,v2,v2,v5,v5,v2,v3,v4,v4,v3}

解答：

（1）

（2）

10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样的图。

（1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4

解答：（1）（3）不存在，因为有奇数个奇度顶点 。

14、设G是n(n2)阶无向简单图，G是它的补图，已知(G)k1,(G)k2，求(G)，(G)。

解答：(G)n1k2；(G)n1k1。

15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。

解答：

（c）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1

（d）同构，同构函数为

12f(x)345解答：

（1）三条边一共提供6度；所以点度序列可能是

xaxbxc

xdxe16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。

①3，3，0，0，0，0；②3，2，1，0，0，0；③3，1，1，1，0，0；④2，2，2，0，0，0；⑤2，2，1，1，0，0；⑥2，1，1，1，1，0；⑦1，1，1，1，1，1；

由于是简单图，①②两种情形不可能

图形如下： （2）三条边一共提供6度，所以点度序列可能为

①3，3，0；②3，2，1；③2，2，2

由于是简单图，①②两种情形不可能

21、在图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）构成通路，且为初级通路，因为点不重复

（2）构成了回路，但是不为简单回路和初级回路，因为有重复的边(a,b)

（3）构成了初级通路，因为点不重复；

（4）不构成通路，因为边(a,c)不存在；

（5）构成通路，但是不为简单通路和初级通路，因为有重复的边(d,c)

（6）构成了回路，但是不为简单回路和初级回路，因为有重复的边(d,b)

（7）构成了初级通路；

（8）简单通路，但是不为初级通路，有重复边。

23、用Dijkstra标号法求图9.22中各图从顶点v1到其余各点的最短路径和距离。

解答

步骤

1

2

3

4

5

6

7

v1

v2

v3

v4

v5

v6

(v1,)

(v1,)

(v1,)

v7

(v1,)

v8

(v1,)

(v1,0)*

(v1,6)

(v1,3)*

(v1,)

(v1,)

(v1,6)

(v1,6)*

(v3,5)*

(v3,8)

(v3,11)

(v1,)

(v3,11)

(v4,11)

(v3,11)

(v4,11)

(v5,7)*

(v4,11)

(v4,6)

(v4,6)*

(v2,12)

(v2,12)

(v2,12)

(v2,12)*

(v7,10)*

v1到v2最短路为v1v2，路长为6；

v1到v3最短路为v1v3，路长为3；

v1到v4最短路为v1v3v4，路长为5； v1到v5最短路为v1v3v4v5，路长为6；

v1到v6最短路为v1v2v6，路长为12；

v1到v7最短路为v1v3v4v5v7，路长为7；

v1到v8最短路为v1v3v4v5v7v8，路长为10；

（2）略。

25、图9.23中各图有几个连通分支？给出它们所有的连通分支。

解答：

（a）有两个连通分支：aec和bdf；

（b）有三个连通分支：abd、c和ef；

（c）连通图，只有一个连通分支；

（d）两个连通分支：afbgd和ech。

38、写出图9.27的关联矩阵。

1100000010111000解答：00010001

0000111101100110

40、写出图9.29中各图的邻接矩阵。

解答：

10(a)1002001010; (b)000110100000101000001

0100101000A00210010

00101141、设有向图DV,E，其中V{v1,v2,v3,v4}，其邻接矩阵为

试求出D中各顶点的入度和出度。

解答：出度：v1:3;v2:1;v3:1;v4: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道v1长度为1，2，3，4的通路各有几条？

（3）D中长度为4的通路有多少条？其中长为4的回路有多少条？

（4）D中长度小于或者等于4的通路有多少条？其中多少条为回路？

（5）写出D的可达矩阵。

10解答：M10524M42200110102，则M1001010122032120013，M22210001122210，

2110642221，

432221（1）D中v1道v4长度为1，2，3，4的通路各有0，0，2，2条；

（2）D中v1道v1长度为1，2，3，4的通路各有1，1，3，5条；

（3）D中长度为4的通路有44条；其中长为4的回路有11条.

（4）D中长度小于或者等于4的通路有88条；其中22条为回路。

11（5）写出D的可达矩阵为11

111111。

111111P181:习题十

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4x182x144xx2

所以有2个4度分支点。

4、无向树T有ni(i2,3,...,k)个i度分支点，其余顶点都为树叶，问T有几片树叶？

解答：设有x片树叶，共有xkn个顶点，那么有xnii2i2kkikki1条边，

而共有xin度，由握手定理可知xinii2i22(x1ni)

i2所以有x2(i2)n。

ii2k15、已知n阶m条边的无向图G是k(k2)棵树组成的森林。证明：mnk。

证明：

方法一：对变量k进行归纳

当k1是，因为是一棵树，显然成立；

假设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个顶点和mi条边，i1,2,...,k，则有

mmi，nni，mini1，即可得证。

i1i1kk 19、求图10.17中两个带权图的最小生成树。

解答：

P204:习题十一

1、判断图11.22中哪些是欧拉图？哪些是半欧拉图？对欧拉图给出一条欧拉回路。对半欧拉图给出一条欧拉通路。对不是的，说明不是欧拉图或半欧拉图的理由。

解答：（a）为欧拉图，全为偶度顶点；（b）为半欧拉图，1，2两个顶点点度为3，其它为偶数。 2、判断图11.23中哪些是欧拉图？哪些是半欧拉图？对欧拉图给出一条欧拉回路。对半欧拉图给出一条欧拉通路。对不是的，说明不是欧拉图或半欧拉图的理由。

解答：（a）为半欧拉图，a,c两点的出度和入度都相等；b点的入度比出度大1；c点的入度比出度小1.

（b）为欧拉图，每个顶点的入度和出度都相等。

3、判断命题的真假。

（1）完全图Kn是欧拉图。

（2）n(n2)阶有向完全图是欧拉图。

（3）当r,s为正偶数时，完全二部分图Kr,s是欧拉图。

解答：（1）为假，因为当n为偶数时，每个点的点度都为奇数。

（2）真；有向完全图的出度和入度必然相等。

（3）真，完全二部分图Kr,s中，一部分点的点度全为r,另外一部分点的点度全为s。

10.说明图11.25中各图不是哈密顿图，也不半哈密顿图的理由。

解答：（a）删掉画圈的3个顶点，还剩下5个连通分支；

（b）删掉画圈的4个顶点，还剩下6个连通分支。

由定理11.2和11.3可知不是哈密顿图，也不半哈密顿图。

11、设G是无向连通图，证明：若G中有桥或者割点，则G不是哈密顿图。

证明：

① 若G中有者割点v，取V{v}，则p(GV)2|V|，由书中定理11.2可知，G不是哈密顿图。

② 若G中有者割边e(v1,v2)，

如果v1和v2的点度都为1，则该图只有一条边，显然不为哈密顿图；

③ 如果v1和v2的点度至少有一个大于1，不妨设v1的点度大于1，取V{v1}，则p(GV)2|V|，由书中定理11.2可知，G不是哈密顿图。