本文格式为Word版，下载可任意编辑离散数学(图论部分)1 离散数学（图论片面）1-4章习题课 1. 证明：在10个人中，或有3人彼此熟悉，或有4人互不熟悉 证：设x为10人中之任意某人，那么在余下9人中：(1) x至少熟悉其中4人，或(2) x至多熟悉其中3人（即至少不熟悉其中6人），两者必居其一 (1) 若此x熟悉的4人互不相识，命题得证；否那么，彼此熟悉的2人加上x构成彼此熟悉的3人，命题得证 (2) 若此x不熟悉的6人中有3人彼此熟悉，命题得证；否那么，由Ramsey(3,3)=6知，此6人中至少有3人互不熟悉，此3人加上x为互不熟悉的4人，命题得证 2. 设 (a) V={a,b,c,d}，A={,,,,} (b) V={a,b,c,d,e}，E={(a,b),(a,c),(b,c),(d,e)} 画出上述图的图解 解：略 3. 试找出K3的全部子图，并指出哪些是生成子图 解：K3共有17个子图 4. 证明：在至少有2人的团体中，总存在2个人，他们在这个团体中恰有一致数目的挚友 解：在n个人的团体中，各人可能有的挚友数目为0, 1, 2, 3, …, n?1，共n个数，但其中0和n?1 不能共存，故n个人事实上可能的挚友数目只有n?1个。
由鸽巢原理，命题得证 5. 某次宴会上大量人彼此握手证明：必有偶数个人握了奇数次手 证：以人为顶点，握手关系为邻接关系构造一个无向图由图的性质，奇数度的顶点必为偶数个，即握了奇数次手的人数必为偶数 6. 证明：Ramsey(3,4)=9提示：题1的推广） 证：在9个人中，不成能每个人都恰好熟悉其他的3个人（即图的9个顶点不 可能每个顶点的度都为3，否那么违反图的奇数度的顶点必为偶数个的性质）设x不会恰好熟悉其他的3个人（即deg(x)?3），那么在余下8人中：：(1) x至少熟悉其中4人，或(2) x至多熟悉其中2人（即至少不熟悉其中6人），两者必居其一由题1的过程，命题得证 7. 证明：图G=(V, E)，n=|V|，m=|E|若m?(n?1)(n?2)，那么G连通 证：利用反证法设G可分解为不连通的非空的两片面G1= (V1, E1 )、G2 = (V2, E2 )，并设 n1=|V1|?0，m1=|E1|， n2=|V2|?0，m2=|E2| 那么 n=n1+n2，m=m1+m2 若 G1为完全图，那么 m1=n1(n1?1)，故 m1?n1(n1?1) 若 G2为完全图，那么 m2=n2(n2?1)，故 m2?n2(n2?1) 故：m= m1+m2 ?n1(n1?1)+n2(n2?1) =(n?1)(n?2)+(n1?1)(n1?n+1) 又：1?n1?n?1 故：(n1?1)(n1?n+1)?0 即：m?(n?1)(n?2) 与条件m?(n?1)(n?2) 冲突。
8. 证明：图G = ( V, E )，n=|V|，m=|E|若G连通，那么m?(n?1) 证一：对n做归纳 n=2时，m=1?n?1成立 设 n=k时，命题成立 当n=K+1时， 由于G连通，任意顶点的度?1； 12121212121212121212(1) 若任意顶点的度?2，那么 2m=?deg(vi) ?2n，此时 m?n?n?1，命题成立 (2) 否那么，若有某顶点u的度为1，从图中去掉该顶点以及其关联边，得到的新图 G1 = (V1, E1) 依旧连通，且 n1=|V1|= n?1=K，m1=|E1|= m?1 由归纳假设，对图G1有 m1?(n1?1) 即 m?1?(n?1?1) 或 m?(n?1) 由归纳原理，命题得证 证二：由于G连通，设T= ( V, E? ) 是G的一棵生成树，那么 |E?|=n?1，而 m?|E?|，故 9. 证明：n个人中，若任何2人合在一起熟悉其他n?2个人，那么他们可以排成一排，使除首尾2人外，其余的人都和相邻的人熟悉 证：以人为顶点，熟悉关系为邻接关系构造一个无向图，问题转化为议论得志条件的图中Hamilton道路的存在性。
从图中任取2个顶点x和y，记deg(x,y) 为 {x,y} 与其他顶点的邻接边数目由题意，有 deg(x,y)?n?2，这里的n?2由除了x和y外的n?2顶点中每个顶点付出一条与x或y邻接的边得到 (1) 若x与y熟悉，那么 deg(x)+deg(y) = deg(x,y)+2 ? n?2+2 = n ? n?1 (2) 若x与y不熟悉，设x熟悉z，z?y，由题意x与z合在一起熟悉包括y的其他n?2个人，所以只能z也熟悉y，即在图中，顶点z与x和y同时邻接由之前deg(x,y) ? n?2的议论可得： deg(x,y) ? n?2+1 = n?1， 故 deg(x)+deg(y) = deg(x,y) ? n?1 综上，对任意顶点x和y，有deg(x)+deg(y) ? n?1，由Hamilton道路存 在的充分条件知图中存在一条Hamilton道路，命题得证 10. 用Warshall算法求下图的道路矩阵： 解：见课件的举例 11. 若树中恰有2个顶点的度为1，那么此树为一条链 证：设 T= (V, E) 为一棵树，n=|V|，m=|E|，那么 m=n?1 故：?deg(vi)?2m?2(n?1) 且 deg (vi) ?0 (i =1..n) vi?V不妨设 deg (v1)= deg (vn)=1， 那么 ?deg(v)?2(n?1)?2?2(n?2)且 deg (vi) >1 (i =2..n?1) ii?2n?1所以只能 deg (vi) =2 (i =2..n?1) 即此树为从v1到vn的一条路。
12. 若树中有一顶点的度为k，那么树中至少有 k个度为1的点 证：设 T= (V, E) 为一棵树，n=|V|，m=|E|，那么 m=n?1 故： ?deg(v)?2m?2(n?1) 且 deg (v) ?0 (i =1..n) ii?1ni 不妨设 deg (vn) =k，那么 ?deg(v)?2(n?1)?k ii?1n?1设树中有p个度为1的顶点：deg (vn?1) = deg (vn?2)= deg (vn-p)=1 n?p?1那么 或 ?deg(v)?p?2(n?1)?k ii?1n?p?1i?1?deg(v)?2(n?1)?k?p i对余下的n?p?1个顶点，每个顶点的度至少为2，即 n?p?1 ?degv(?)ii?1n2?(p? 1)所以 2(n?1)?k?p ? 2(n?p?1) 解不等式得：p ? k 13. 设连通图G=(V, E)，T=(V, E(T))和T'=(V, E(T'))是G的两棵不同生成树且 e?E(T)?E(T')，那么存在一条边 e'?E(T')?E(T)，使得 T?e+e' 和 T'?e'+e 都是G的生成树。
证：从T中去掉边e，那么T被分成不连通的两片面，设其顶点集分别为V1和V2在T'中必存在连接V1和V2的边，记为e'?E(T') ∵ e?E(T)?E(T') 即 e?E(T') ∴ e'? e 又：若e'?E(T)，那么e不是T中割边，与T是一棵树冲突 ∴ e'?E(T) 即 e'?E(T')?E(T) 考察 T+e'，e和e' 在其中唯一的回路上，因此T?e+e' 构成G的一棵生成树 同理，考察 T'+e，可知 T'?e'+e 也构成G的一棵生成树 14. 设图G=(V, E)，定义?(G)=min{deg(v), v?V}为G的最小度（类似可以定义 ?(G)=max{deg(v), v ?V}为G的最大度）若G是简朴图，?(G) ? k，T是一棵含k条边的树，那么在G中存在与T同构的子图提示：对k作归纳 证：对 k作归纳 易知 k=1时结论成立 设 k=p时结论成立 当 k=p+1时， G是简朴图，?(G)?p+1设树T含p+1条边（p+2个顶点），v0是T的一个叶子结点，u是v0的邻接点，其余顶点编号为v1~vp记e=(u, v0)，T0=T?e，那么G和T0符合归纳假设的条件，G中存在与T0同构的子图T0?。
将T0? 的p+1个顶点与T0的顶点对应，编号为u?, v1?~vp? 考察顶点u?，由于deg(u?)?p+1，可见u?至少与除了v1?~vp? 之外的一个点邻接将该点编号为v0?，记 e?=(u?, v0?)，构造的T?=T0?+e? 与T同 — 6 —。