资源描述
作业答案:图论部分P165:习题九1、 给定下面4个图(前两个为无向图,后两个为有向图)的集合表示,画出它们的图形表示。(1),(2),(3)(4)解答:(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是阶无向简单图,是它的补图,已知,求,。解答:;。15、图9.19中各对图是否同构?若同构,则给出它们顶点之间的双射函数。解答:(c)不是同构,从点度既可以看出,一个点度序列为4,3,3,3,3而另外一个为4,4,3,3,1(d)同构,同构函数为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);(2);(3);(4)(5);(6);(7);(8)解答:(1)构成通路,且为初级通路,因为点不重复(2)构成了回路,但是不为简单回路和初级回路,因为有重复的边(3)构成了初级通路,因为点不重复;(4)不构成通路,因为边不存在;(5)构成通路,但是不为简单通路和初级通路,因为有重复的边(6)构成了回路,但是不为简单回路和初级回路,因为有重复的边(7)构成了初级通路;(8)简单通路,但是不为初级通路,有重复边。23、用Dijkstra标号法求图9.22中各图从顶点到其余各点的最短路径和距离。解答步骤1234567到最短路为,路长为6;到最短路为,路长为3;到最短路为,路长为5;到最短路为,路长为6;到最短路为,路长为12;到最短路为,路长为7;到最短路为,路长为10;(2)略。25、图9.23中各图有几个连通分支?给出它们所有的连通分支。解答:(a)有两个连通分支:和;(b)有三个连通分支:、和;(c)连通图,只有一个连通分支;(d)两个连通分支:和。38、写出图9.27的关联矩阵。解答:40、写出图9.29中各图的邻接矩阵。解答:(a); (b)41、设有向图,其中,其邻接矩阵为试求出中各顶点的入度和出度。解答:出度: 入度:43、有向图D如图9.29(a)所示(1)D中道长度为1,2,3,4的通路各有几条?(2)D中道长度为1,2,3,4的通路各有几条?(3)D中长度为4的通路有多少条?其中长为4的回路有多少条?(4)D中长度小于或者等于4的通路有多少条?其中多少条为回路?(5)写出D的可达矩阵。解答:,则,(1)D中道长度为1,2,3,4的通路各有0,0,2,2条;(2)D中道长度为1,2,3,4的通路各有1,1,3,5条;(3)D中长度为4的通路有44条;其中长为4的回路有11条.(4)D中长度小于或者等于4的通路有88条;其中22条为回路。(5)写出D的可达矩阵为。P181:习题十1、 图10.14中的哪些图是树?解答:(a)是树;(b)不是树,因为不连通。3、无向树T有8片树叶,2个3度分支点,其余分支点都是4度顶点,问T有几个4度分支点?请画出3棵非同构的这种无向树。解答:设有个4度分支点,则T共有个顶点。那么有条边。由握手定理有所以有2个4度分支点。4、无向树T有个i度分支点,其余顶点都为树叶,问T有几片树叶?解答:设有片树叶,共有个顶点,那么有条边,而共有度,由握手定理可知所以有。15、已知n阶m条边的无向图G是棵树组成的森林。证明:。证明:方法一:对变量进行归纳当是,因为是一棵树,显然成立;假设n阶m条边的无向图G是棵树组成的森林,有;那么对于n阶m条边的无向图G是棵树组成的森林,在任意两棵树中分别找一点进行连一条边,那么得到的图则为n阶m+1条边的无向图G是棵树组成的森林,那么,所以。方法二:设棵树中,分别有个顶点和条边,则有,即可得证。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)完全图是欧拉图。(2)阶有向完全图是欧拉图。(3)当r,s为正偶数时,完全二部分图是欧拉图。解答:(1)为假,因为当n为偶数时,每个点的点度都为奇数。(2)真;有向完全图的出度和入度必然相等。(3)真,完全二部分图中,一部分点的点度全为r,另外一部分点的点度全为s。10.说明图11.25中各图不是哈密顿图,也不半哈密顿图的理由。解答:(a)删掉画圈的3个顶点,还剩下5个连通分支;(b)删掉画圈的4个顶点,还剩下6个连通分支。由定理11.2和11.3可知不是哈密顿图,也不半哈密顿图。11、设G是无向连通图,证明:若G中有桥或者割点,则G不是哈密顿图。证明: 若G中有者割点,取,则,由书中定理11.2可知,G不是哈密顿图。 若G中有者割边,如果和的点度都为1,则该图只有一条边,显然不为哈密顿图; 如果和的点度至少有一个大于1,不妨设的点度大于1,取,则,由书中定理11.2可知,G不是哈密顿图。
展开阅读全文