离散数学习题课 此页可以删除
目录 Contents 1 作业讲解 2 课堂练习
目录 Contents 1 作业讲解 2 课堂练习
习题一 2.简单图G中,如果m>1/2(n-1)(n-2),证明G不存在孤立节点。 知识点:图的边,孤立节点
习题一 拉塞姆定理:任意6个人必定3个是彼此认识或彼此不认识. 证明: 在平面上用6个点A、B、C、D、E、F分别代表参加集会的任意6个人.如果两人以前彼此认识,那么就在代表他们的两点间连成一条红线;否则连一条蓝线.考虑A点与其余各点间的5条连线AB,AC,…,AF,它们的颜色不超过2种.根据抽屉原理可知其中至少有3条连线同色,不妨设AB,AC,AD同为红色.如果BC,BD ,CD 3条连线中有一条(不妨设为BC)也为红色,那么三角形ABC即一个红色三角形,A、B、C代表的3个人以前彼此相识:如果BC、BD、CD 3条连线全为蓝色,那么三角形BCD即一个蓝色三角形,B、C、D代表的3个人以前彼此不相识.
习题一 用图论语言来说,本题等价于对K9(9个点的完全图)的边进行红蓝染色,那么必有一个红色K3或一个蓝色K4。下证之: (1)如果K9中有一个点v1引出至少4条红边,不妨设v1v2,v1v3,v1v4,v1v5为红边。这时 v2,v3,v4,v5四个点所成的K4中或者每条边都是蓝色(即存在蓝色K4),或者至少有一条边是红色(即存在红色K3)。 (2)如果K9中每个点引出的红边少于4条,那么每点至少引出5条蓝边。 由于蓝边总数的2倍>=5*9=45,从而蓝边总数的2倍>=46,从而至少有一点v1引出6条蓝边,设为v1v2,v1v3,v1v4,v1v5,v1v6,v1v7为蓝边,这时v2,v3...v7所成的K6中必有一个同色三角形,如果是红色,则存在红色K3,如果是蓝色,并上v1点后形成蓝色K4。
习题三 1.一棵树有n2个结点的度为2,n3个结点的度为3 ……,nk个结点的度为k, 问有几个度为1的结点。
习题三 2.证明树中最长道路的两个端点一定都是树叶。 证明:设L 是树T 的一条最长路,L 中的结点依次为 v1, v2 , …,vk。因为L 中各结 点都有边相连,所以它们的度数均大于或等于1。 若deg (v1)>1, 则除了边(v1, v2)外,还存在边(v1, v’) 。因为树中不存在回 路,故v’不属于集合{ v1, v2 , …, vk },于是,(v’,v1, v2 , …, vk)是T 的一条新的路, 其长度比L 更长。这与L 是T的最长路矛盾。 所以deg (v1)=1,类似可证deg (vk)=1。
习题三 14.给出字符串state act as a seat (a)最优二进制编码 (b)如果不带空格,求该字符串的最优二进制编码 (a) 各字符出现的次数为 s t a e c 空格: 3 4 5 1 1 4
习题三 14.给出字符串state act as a seat (a)最优二进制编码 (b)如果不带空格,求该字符串的最优二进制编码 (a) 各字符出现的次数为 s t a e c 空格: 3 4 5 1 1 4
习题三 16.求最短树 用Kruskal 算法。先将权排序,而后按权由小到大选边7 条(构成回路时所选边 不放入),可得一棵最小生成树(总权为22):
目录 Contents 1 作业讲解 2 课堂练习
题目答案
题目答案
题目答案
题目答案
谢 谢!