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

作业答案：图论部分

P165:习题九

（1）G??V,

（1）G

??V,E?，V?{v,v,v,v,v}，E?{(v,v),(v,v),(v,v),(v,v),(v,v)}

1

1 1 1 1 2 3 4 5 1 1 2 2 3 3 4 3 3 4 5

（2）G

??V,E ?，V ?V，E?{(v,v),(v,v),(v,v),(v,v),(v,v)}

2

2 2 2 1 1 1 2 2 3 3 4 4 5 5 1

（3）D

??V,E ?,V ?V,E ?{?v,v ?,?v,v ?,?v,v ?,?v,v ?,?v,v?}

1

3 3 3 1 3 1 2 2 3 3 2 4 5 5 1

（4）D

??V,E ?,V ?V,E ?{?v,v ?,?v,v ?,?v,v ?,?v,v ?,?v,v ?}

2

解答：

4 4 4 1 3 1 2 2 5 5 2 3 4 4 3

（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)?k

1

,?(G)?k

2

，求?(G)，

?(G)。

解答：?(G)?n?1?k

2

；?(G)?n?1?k。

1

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

解答：

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

3，3，1

同构，同构函数为

?1

?2

?f(x)??3

?

?4

?

??5

x?ax?bx?cx?dx?e

16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。解答：

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

①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；由于是简单图，①②两种情形不可能

图形如下：

三条边一共提供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）构成通路，且为初级通路，因为点不重复

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

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

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

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

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

构成了初级通路；

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

23、用Dijkstra标号法求图9.22中各图从顶点v

1

到其余各点的最短路径和距离。

vv

v

v

v

v

v

v

v

v

1

2

3

4 5

6

7

8

1 (v,0)* (v,6) (v,3)* (v,?) (v,?)

(v,?)

(v,?)

(v,?)

1 1 1

2 (v,6)

1

3

1 1

(v,5)* (v

3 3

,8)

1

(v,?)

1

1 1

(v,11) (v,?)

3 1

(v,6)*

1

4

(v,6)

4

(v,?)

1

(v,11) (v

3 4

,11)

(v,6)* (v

4 2

(v

2

(v

,12)

,12)

,12)

(v,11) (v

3 4

(v,7)* (v

5 4

(v

,11)

,11)

,10)*

7

v到v

1 2

v到v

最短路为v

1

最