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

本文格式为Word版，下载可任意编辑——离散数学及其应用图论部分课后习题答案作业答案：图论部分

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?cx?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到其余各点的最短路径和距离。

解答步骤1234567v1v2v3v4v5v6v7v8(v1,0)*(v1,6)(v1,3)*(v1,?)(v1,?)(v1,?)(v1,?)(v1,?)(v1,6)(v3,5)*(v3,8)(v1,?)(v1,?)(v3,11)(v1,?)(v3,11)(v4,11)(v3,11)(v4,11)(v1,6)*(v4,6)(v4,6)*(v2,12)(v2,12)(v2,12)(v5,7)*(v4,11)(v7,10)*(v2,12)*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。