离散数学课后习题答案五.docVIP

第十四章部分课后习题参考答案 5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有多少个顶点？在最少顶点的情况下，写出度数列、。 　　解：由握手定理图G的度数之和为： 　　　　3度与4度顶点各2个，这4个顶点的度数之和为14度。 　　　　其余顶点的度数共有6度。 　　　　其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2, 　　所以，G至少有7个顶点, 出度数列为3,3,4,4,2,2,2,. 7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求， ,. 解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2. ,, 8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？ 解：由握手定理图G的度数之和为： 　　设2度点个，则，，该图有4个顶点. 14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。 (1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化； 18、设G1、G2、G3 所以，G1、G2、G3G有m条边，试求G的补图的边数。 解： 21、无向图G如下图 (1)求G的全部点割集与边割集，指出其中的割点和桥； (2) 求G的点连通度与边连通度。 解：点割集: {a,b},(d) 边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5} ==1 23、求G的点连通度、边连通度与最小度数。 解：、 、 28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？ 解： 得n=6,m=9. 31、设图G和它的部图的边数分别为和，试确定G的阶数。 解： 得 45、有向图D如图 (1)求到长度为1，2，3，4的通路数； (2)求到长度为1，2，3，4的回路数； (3)求D中长度为4的通路数； (4)求D中长度小于或等于4的回路数； (5)写出D的可达矩阵。 解：有向图D的邻接矩阵为： ， (1)到长度为1，2，3，4的通路数为0,2,0,0； (2)到长度为1，2，3，4的回路数为0,0,4,0； (3)D中长度为4的通路数为32； (4)D中长度小于或等于4的回路数10； (4)出D的可达矩阵 第十六章部分课后习题参考答案 1、画出所有5阶和7阶非同构的无向树. 2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点? 解：设3度分支点个，则 ，解得 T有11个顶点 3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。 解：设4度分支点个，则 ，解得 度数列111111113344 4、棵无向树T有 (i=2，3，…，k)个i度分支点，其余顶点都是树叶，问T应该有几片树叶? 解：设树叶片，则 ，解得 评论：2，3，4题都是用了两个结论,一是握手定理，二是 5、n(n≥3)阶无向树T的最大度至少为几？最多为几？ 解：2，n-1 6、若n(n≥3)阶无向树T的最大度 =2，问T中最长的路径长度为几？ 解：n-1 7、证明：n(n≥2) 阶无向树不是欧拉图. 证明：无向树没有回路，因而不是欧拉图。 8、证明：n(n≥2) 阶无向树不是哈密顿图. 证明：无向树没有回路，因而不是哈密顿图。 9、证明：任何无向树T都是二部图. 证明：无向树没有回路，因而不存在技术长度的圈，是二部图。 10、什么样的无向树T既是欧拉图，又是哈密顿图? 解：一阶无向树 14、设e为无向连通图G中的一条边， e在G的任何生成树中，问e应有什么性质? 解：e是桥 15、设e为无向连通图G中的一条边， e不在G的任何生成树中， 问e应有什么性质? 解：e是环 23、已知n阶m条的无向图 G是k(k≥2)棵树组成的森林，证明：m = n-k.； 证明：数学归纳法。k=1时, m = n-1，结论成立； 设k=t-1(t-1)时，结论成立，当k=t时, 无向图 G是t棵树组成的森林,任取两棵树，每棵树任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m = n-（k-1）. 所以原图中m = n-k 得证。 24、在图16.6所示2图中，实边所示的生成子图T是该图的生成树. (