《离散数学及其应用图论部分课后习题答案》由会员分享，可在线阅读，更多相关《离散数学及其应用图论部分课后习题答案（11页珍藏版）》请在金锄头文库上搜索。
1、作业答案：图论部分P165:习题九1、 给定下面 4 个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表示。（1） ， ，1,GVE12345,v234()()()v（2） ， ，,21123451,(,),(,),Evvv（3） 133,D3 245（4） 2441,VE125343,解答：（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 是 阶无向简单图， 是它的补图，已知 ，求
2、(2)nG12(),()Gk， 。()解答： ； 。21k1()nk15、图 9.19 中各对图是否同构？若同构，则给出它们顶点之间的双射函数。解答：（c）不是同构，从点度既可以看出，一个点度序列为 4，3，3，3，3 而另外一个为4，4，3，3，1（d）同构，同构函数为 12()345xabfxcdxe16、画出所有 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，0，0，0；2，2，1，1，0，0；2，1，1，1，1，0；1，1，1，1，1
3、，1；由于是简单图，两种情形不可能图形如下：（2）三条边一共提供 6 度，所以点度序列可能为3，3，0；3，2，1；2，2，2由于是简单图，两种情形不可能21、在图 9.20 中，下述顶点序列是否构成通路？哪些是简单通路？哪些是初级通路？哪些是回路？哪些是简单回路？哪些是初级回路？（1） ；（2） ；（3） ；（4）,abcde,abed,adceb,;dace（5） ；（6） ；（7） ；（8）,abcde,adbec,cdab,abce解答：（1）构成通路，且为初级通路，因为点不重复（2）构成了回路，但是不为简单回路和初级回路，因为有重复的边 (,)（3）构成了初级通路，因为点不重复；（4
4、）不构成通路，因为边 不存在；(,)ac（5）构成通路，但是不为简单通路和初级通路，因为有重复的边 (,)dc（6）构成了回路，但是不为简单回路和初级回路，因为有重复的边 b（7）构成了初级通路；（8）简单通路，但是不为初级通路，有重复边。23、用 Dijkstra 标号法求图 9.22 中各图从顶点 到其余各点的最短路径和距离。1v解答步骤 1v23v45v67v81 *(,0)1(,6)*1(,)1(,)1(,)1(,)1(,)1(,)2 v*3,v38v3v3 *1(,)4(,6)1(,)(,)4(,)4 *,v231v5 (,)*5(,7)4(,)6 2v*7,0v7 *(,1)到 最
5、短路为 ，路长为 6；1v212v到 最短路为 ，路长为 3；33到 最短路为 ，路长为 5；1414到 最短路为 ，路长为 6；1v51345vv到 最短路为 ，路长为 12；626到 最短路为 ，路长为 7；1713457到 最短路为 ，路长为 10；v8 8vv（2）略。25、图 9.23 中各图有几个连通分支？给出它们所有的连通分支。解答：（a）有两个连通分支： 和 ；aecbdf（b）有三个连通分支： 、 和 ；（c）连通图，只有一个连通分支；（d）两个连通分支： 和 。fgech38、写出图 9.27 的关联矩阵。解答：10011000 40、写出图 9.29 中各图的邻接矩阵。解
6、答：(a) ; (b)1200110041、设有向图 ，其中 ，其邻接矩阵为,DVE1234,v01A试求出 中各顶点的入度和出度。D解答：出度： 1234:;:;vv入度： 0243、有向图 D 如图 9.29（a）所示（1）D 中 道 长度为 1， 2，3，4 的通路各有几条？1v4（2）D 中 道 长度为 1， 2，3，4 的通路各有几条？（3）D 中长度为 4 的通路有多少条？其中长为 4 的回路有多少条？（4）D 中长度小于或者等于 4 的通路有多少条？其中多少条为回路？（5）写出 D 的可达矩阵。解答： ，则 ， ，120M210M3210M，456213（1）D 中 道 长度为
7、1， 2，3，4 的通路各有 0，0，2，2 条；1v4（2）D 中 道 长度为 1， 2，3，4 的通路各有 1，1，3，5 条；（3）D 中长度为 4 的通路有 44 条；其中长为 4 的回路有 11 条.（4）D 中长度小于或者等于 4 的通路有 88 条；其中 22 条为回路。（5）写出 D 的可达矩阵为 。1P181:习题十1、 图 10.14 中的哪些图是树？解答：（a）是树；（b）不是树，因为不连通。3、无向树 T 有 8 片树叶，2 个 3 度分支点，其余分支点都是 4 度顶点，问 T 有几个 4 度分支点？请画出 3 棵非同构的这种无向树。解答：设有 个 4 度分支点，则 T
8、 共有 个顶点。那么有 条边。由x8210x9x握手定理有 (9)42x所以有 2 个 4 度分支点。4、无向树 T 有 个 i 度分支点，其余顶点都为树叶，问 T 有几片树叶？(2,3.)ink解答：设有 片树叶，共有 个顶点，那么有 条边，x2ixn21kixn而共有 度，由握手定理可知2kiin22()kki ii所以有 。2()kiix15、已知 n 阶 m 条边的无向图 G 是 棵树组成的森林。证明： 。(2)kmnk证明：方法一：对变量 进行归纳k当 是，因为是一棵树，显然成立；1k假设 n 阶 m 条边的无向图 G 是 棵树组成的森林，有 ；1k(1)nk那么对于 n 阶 m 条
9、边的无向图 G 是 棵树组成的森林，在任意两棵树中分别找一点进行连一条边，那么得到的图则为 n 阶 m+1 条边的无向图 G 是 棵树组成的森林，那么 ，所以 。1()kk方法二：设 棵树中，分别有 个顶点和 条边， ，则有iim1,2.ik， ， ，即可得证。1kii1kin1iin19、求图 10.17 中两个带权图的最小生成树。解答：P204:习题十一1、判断图 11.22 中哪些是欧拉图？哪些是半欧拉图？对欧拉图给出一条欧拉回路。对半欧拉图给出一条欧拉通路。对不是的，说明不是欧拉图或半欧拉图的理由。解答：（a）为欧拉图，全为偶度顶点；（b）为半欧拉图，1，2 两个顶点点度为 3，其它为
10、偶数。2、判断图 11.23 中哪些是欧拉图？哪些是半欧拉图？对欧拉图给出一条欧拉回路。对半欧拉图给出一条欧拉通路。对不是的，说明不是欧拉图或半欧拉图的理由。解答：（a）为半欧拉图，a,c 两点的出度和入度都相等； b 点的入度比出度大 1；c 点的入度比出度小 1.（b）为欧拉图，每个顶点的入度和出度都相等。3、判断命题的真假。（1）完全图 是欧拉图。nK（2） 阶有向完全图是欧拉图。()（3）当 r,s 为正偶数时，完全二部分图 是欧拉图。,rsK解答：（1）为假，因为当 n 为偶数时，每个点的点度都为奇数。（2）真；有向完全图的出度和入度必然相等。（3）真，完全二部分图 中，一部分点的点
11、度全为 r,另外一部分点的点度全为 s。,rs10.说明图 11.25 中各图不是哈密顿图，也不半哈密顿图的理由。解答：（a）删掉画圈的 3 个顶点，还剩下 5 个连通分支；（b）删掉画圈的 4 个顶点，还剩下 6 个连通分支。由定理 11.2 和 11.3 可知不是哈密顿图，也不半哈密顿图。11、设 G 是无向连通图，证明：若 G 中有桥或者割点，则 G 不是哈密顿图。证明： 若 G 中有者割点 ，取 ，则 ，由书中定理 11.2 可知，G 不vV()2|pV是哈密顿图。 若 G 中有者割边 ，12(,)e如果 和 的点度都为 1，则该图只有一条边，显然不为哈密顿图；1v2 如果 和 的点度至少有一个大于 1，不妨设 的点度大于 1，取 ，则1v1Vv，由书中定理 11.2 可知，G 不是哈密顿图。()|pV
