资源描述
作业答案：图论部分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不是哈密顿图。
展开阅读全文