习题十一
1、设一个树中度为k的结点数是nk(2?k),求它的叶的数目
解：设T中叶结点数目为t，那么根据握手定理，及数的点边关系可以得到： n = t + n2 + n3 + ? + nk (1) Σd(v) = 2m = t + 2n2 + 3n3 + ? + knk = 2(n-1) (2) 所以：t + 2n2 + 3n3 + ? + knk = 2（t + n2 + n3 + ? + nk）- 2 t = n3 + 2n4 +?+(k-2)nk + 2
2、证明：树T中最长简单道路的起点和终点必都是T的叶
证明:
a) 首先证明在T中的任意最长道路P中，其起点u和终点v的所有邻结点必然在
P中，否则此道路可以变长，与最长条件矛盾
b) 假设在T中存在最长道路P,其起点u或终点v不是叶结点(假设是u)，那么
d(u)>1，及u至少有两个邻结点u1,u2，他们都将出现在道路中，既P = uu1?u2?v，因为u2是u的邻结点，所以在T中就存在C=uu1..u2u的简单回路，与树的基本性质矛盾，所以u,v必是叶结点
10、设e是连通图G的一条边，证明：e是G的割边当且仅当e含于G的每个生成树中
证明：
a) e是G的割边 ? e含于G的每个生成树中
假设e不包含在G的生成树T’中，那么删除e边后，T’依然包含在G-{e}中，因为T’连通，所以G-{e}连通，与e是割边矛盾，所以e必包含在G的任何生成树中 b) e含于G的每个生成树中 ? e是G的割边
假设e不是割边，那么G-{e}依然连通，所以存在生成数T’，当然T’也是G的生成树，但e不包含在T’中，与题设矛盾，因此e是G的割边
12、略
23、略（参考课堂ppt）讲解
习题十二
1、证明：图12-7中的图都是平面图
略（只需要画处其平面图的形式即可）
3、设G是阶数不小于11的图，证明：G或G’(代表G的补图)中至少有一个是非平面图
证明：假设G和G’都是平面图，因为m(G) + m(G’) = n(n-1)/2,因此至少有一图的边至少为n(n-1)/4，根据平面图边与点的关系，n(n-1)/4 ? 3n – 6，得到n1 -13n + 24 ? 0,因此 n ? 10, 与题设矛盾；因此必有一图为非平面图
5、证明：少于30条边的简单平面图至少有一个顶点的度不大于4
证明：少于30条边的简单平面图所有的定点的度都大于等于5，那么根据握手定理和平面图的性质有：
5n ? 2m （1）
m ? 3n – 6 （2） ? 5n ? 6n – 12 ? n ? 12 根据（1）式，60 ? 2m，既 m ? 30 与题设矛盾，因此至少有一个顶点的度不大于4
7、证明：对K3,3的任意一条边e，K3,3-e是平面图；同样，对K5的任何边e，K5-e也是平面图
证明：因为K3,3的任意一条边ei,ej，K3,3-ei,K3,3-ej都是同构的，而根据题1（a）的结论，我们可以平面嵌入它，因此K3,3-e是平面图；同理，K5-e也是平面图
9、如果一平面图于其对偶图同购，则称这个平面图为自对偶图，推导自对偶图必须满足的结点数n与边数m的关系，并找出一些自对偶图
解：如果一个图是平面图，那么满足欧拉公式：
n – m + f = 2 （1） 其对偶图也是平面图，因此也应满足欧拉公式：
n* -m* + f* = 2 (2) 因为对偶关系，因此： n = f* f = n* 又因为此二图同构，因此
n = n*, m = m*
所以： n = f, 并且 2n – m = 2
据此可以找到一些自对偶图： K1, G(2,2) – 有两种图像， K4
习题十三
1、构造(n,m)欧拉图，使其满足条件：（1）m,n奇偶性相同；（2）m,n奇偶性相反
答：略
2、设G=（V，E）是一个具有2k(k>0)个奇数度结点的连通图。证明：G中必存在k条边不相重的简单道路P1,P2,?,Pk, 使得E=E(P1) ?E(P2) ?? ?E(Pk)
证明：把2k个奇数度结点分成两两一组的k组，然后每组结点新加一条边，所得图为欧拉图，故存在欧拉回路C；然后去掉欧拉回路C中的k条新加入的边，得到k条互无重复边的道路P1,P2,?,Pk, 即为所求
5、在图13-10中求中国邮递员问题的解 解：
v1 2 v5 v10 6 5 4 3 v6 1 v7 1 v8 4 v3
3 v2 2 v11 3 1 v9 5 2 1 1 v4 如上图标号：
图中有4个奇数度结点v1,v6,v9,v3, 求两两之间最短长度： Pv1v6=3 (v1v6), Pv1v9=7 (v1v2v3v4v9), Pv1v3=4 (v1v2v3), Pv6v9=7 (v6v7v8v9), Pv3v6=6 (v3v8v7v6), Pv3v9=3 (v3v4v9), Pv1v6和Pv3v9满足最小性要求，
复制v1v6和v3v4v9的边，图中欧拉回路即为所求解
6、设G是有两个奇数度点的连通图，设计一个构造G的欧拉道路的算法
解：此算法只要在书中欧拉回路的算法中，添加起点为奇数结点即可，详细描述略
9、证明：凡有割点的图都不是哈密顿图
证明：假设e为图G的割点，根据割点的定义，ω(G-e) > 1，因此不满足哈图的必要条件；所以不是哈图
13、假定在n(?2)个人的团体中，任何2人合起来认识其余的n-2个人，证明：
（1）这n个人可以排成一排，使得站在中间的每个人的两旁都是自己认识的人，站在两端的人旁边各有1个认识的人
（2）当n?4时，这n个人可以围成一个圆圈，使得每个人两旁都是自己所认识的人
证明：如果团体中的个人看成是结点，而人于人的关系看成是边，那么就构成一个认识与否的图，对于问题（1），就转化为此图中存在哈道路问题；问题（2），就转化为图中存在哈圈的问题，现说明如下： 在此题中，任何2人合起来认识其余的n-2个人蕴含任何人最多只有一人不认识，因为如果a，不认识b和c,那么b和c就不能认识完剩下的全部人，因此在图既为d(u) ? n-2
那么，任意两个结点u,v，d(u) + d(v) ? n-2 + n -2，因为n?2，所以d(u) + d(v) ? n-1，根据书中定理，此图存在哈道路
如果n?4，那么d(u) + d(v) ? n-2 + n -2 ? n，根据书中定理，此图存在哈圈
习题十四
4、设S={a,b,c},运算“.”由表14-2定义；
判断代数系统
由运算表可知：” ? ”封闭，所以是广群； 由表可知：
?x,y ?S, x?y=y, 所以 (x?y)?z=z,x?(y?z)=x?z=z, 所以结合律成立，所以是半群； 由表可知：
a,b,c皆为左幺元，无右幺元，所以
5、表14-3中所列运算定义在实数集合R上，请在下表的各栏上填上该运算是否具有指定性质 封闭性 结合性 交换性 存在幺元 存在零元 每元有逆元 + √ √ √ √ × √ - √ × × × × × × √ √ √ √ √ × max √ √ √ × × × min √ √ √ × × × |x-y| √ × √ × × × 答：
+：是封闭的，有结合性，可交换，0为幺员，无零元，每个数的相反数为其逆元a,-a -: 是封闭的，没有结合性 （3-2）-1 ≠ 3 - （2-1），不可交换 3-2 ≠ 2-3，没有幺（不可交换），没有零元，没有逆元（无幺）
×：是封闭的，有结合性，可交换，1为幺元，0为零元，0没有逆元 Max:是封闭的，max(max(a,b),c) = max(a,max(b,c)) 有结合性，max(a,b)=max(b,a) 具有交换性，无幺元，无零元，无逆元 Min：（同上）
|x-y|:是封闭的，||5-3|-2| ≠ |5-|3-2|| 没有结合性，|x-y|=|y-x| 可交换，没有幺 |-1-0| ≠ -1，没有零，没有逆
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学习题答案-2015(6)在线全文阅读。
相关推荐：