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

作业答案：图论部分P165:习题九1、给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表示。（1）111,GVE，112345{,,,,}Vvvvvv，11223343345{(,),(,),(,),(,),(,)}Evvvvvvvvvv（2）222,GVE，21VV，11223344551{(,),(,),(,),(,),(,)}Evvvvvvvvvv（3）13331,,,DVEVV31223324551{,,,,,,,,,}Evvvvvvvvvv（4）24441,,,DVEVV31225523443{,,,,,,,,,}Evvvvvvvvvv解答：（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)nn阶无向简单图，G是它的补图，已知12(),()GkGk，求()G，()G。解答：2()1Gnk；1()1Gnk。15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。解答：（c）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1（d）同构，同构函数为12()345xaxbfxxcxdxe16、画出所有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，1；由于是简单图，①②两种情形不可能图形如下：（2）三条边一共提供6度，所以点度序列可能为①3，3，0；②3，2，1；③2，2，2由于是简单图，①②两种情形不可能21、在图9.20中，下述顶点序列是否构成通路？哪些是简单通路？哪些是初级通路？哪些是回路？哪些是简单回路？哪些是初级回路？（1）,,,,,abcdbe；（2）,,,,,abedba；（3）,,,,adceb；（4）,,,,;dbace（5）,,,,,,,abcdebdc；（6）,,,,,,adbecbd；（7）,,,,cdabc；（8）,,,,abceb解答：（1）构成通路，且为初级通路，因为点不重复（2）构成了回路，但是不为简单回路和初级回路，因为有重复的边(,)ab（3）构成了初级通路，因为点不重复；（4）不构成通路，因为边(,)ac不存在；（5）构成通路，但是不为简单通路和初级通路，因为有重复的边(,)dc（6）构成了回路，但是不为简单回路和初级回路，因为有重复的边(,)db（7）构成了初级通路；（8）简单通路，但是不为初级通路，有重复边。23、用Dijkstra标号法求图9.22中各图从顶点1v到其余各点的最短路径和距离。解答步骤1v2v3v4v5v6v7v8v1*1(,0)v1(,6)v*1(,3)v1(,)v1(,)v1(,)v1(,)v1(,)v21(,6)v*3(,5)v3(,8)v1(,)v3(,11)v1(,)v3*1(,6)v4(,6)v1(,)v3(,11)v4(,11)v4*4(,6)v2(,12)v3(,11)v4(,11)v52(,12)v*5(,7)v4(,11)v62(,12)v*7(,10)v7*2(,12)v1v到2v最短路为12vv，路长为6；1v到3v最短路为13vv，路长为3；1v到4v最短路为134vvv，路长为5；1v到5v最短路为1345vvvv，路长为6；1v到6v最短路为126vvv，路长为12；1v到7v最短路为13457vvvvv，路长为7；1v到8v最短路为134578vvvvvv，路长为10；（2）略。25、图9.23中各图有几个连通分支？给出它们所有的连通分支。解答：（a）有两个连通分支：aec和bdf；（b）有三个连通分支：abd、c和ef；（c）连通图，只有一个连通分支；（d）两个连通分支：afbgd和ech。38、写出图9.27的关联矩阵。解答：110000001011100000010001000011110110011040、写出图9.29中各图的邻接矩阵。解答：(a)1200001010010010;(b)000011010000001101000101041、设有向图,DVE，其中1234{,,,}Vvvvv，其邻接矩阵为0210001000010011A试求出D中各顶点的入度和出度。解答：出度：1234:3;:1;:1;:2;vvvv入度：1234:0;:2;:3;:2;vvvv43、有向图D如图9.29（a）所示（1）D中1v道4v长度为1，2，3，4的通路各有几条？（2）D中1v道1v长度为1，2，3，4的通路...