离散数学习题课 此页可以删除.

Presentation on theme: "离散数学习题课 此页可以删除."— Presentation transcript:

1 离散数学习题课 此页可以删除

2 目录 Contents 1 作业讲解 2 课堂练习

3 目录 Contents 1 作业讲解 2 课堂练习

4 习题一 2.简单图G中，如果m>1/2(n-1)(n-2)，证明G不存在孤立节点。 知识点：图的边，孤立节点

5 习题一 拉塞姆定理：任意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个人以前彼此不相识.

6 习题一 用图论语言来说，本题等价于对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。

7 习题三 1.一棵树有n2个结点的度为2，n3个结点的度为3 ……，nk个结点的度为k， 问有几个度为1的结点。

8 习题三 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。

9 习题三 14.给出字符串state act as a seat (a)最优二进制编码 (b)如果不带空格，求该字符串的最优二进制编码
(a) 各字符出现的次数为 s t a e c 空格：

10 习题三 14.给出字符串state act as a seat (a)最优二进制编码 (b)如果不带空格，求该字符串的最优二进制编码
(a) 各字符出现的次数为 s t a e c 空格：

11 习题三 16.求最短树 用Kruskal 算法。先将权排序，而后按权由小到大选边7 条(构成回路时所选边 不放入)，可得一棵最小生成树（总权为22）：

12 目录 Contents 1 作业讲解 2 课堂练习

13 题目答案

14 题目答案

15 题目答案

16 题目答案

17 谢 谢！