离散数学(第30讲习题课5).ppt

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * 主要内容 * 计算机学院 * 第十一章 深刻理解树（六个等价命题）及生成树、树枝、树补的定义，掌握生成树的主要性质，并能灵活应用它们； 熟练地应用 Kruskal 算法求最小生成树； 掌握根树、m叉树、完全m叉树、正则m叉树、最优树的概念,熟练掌握 Huffman 算法，并使用它求最优二叉树； 第十二章 深刻理解平面图、面、对偶图的定义； 熟记欧拉公式和二个平面图的必要条件, 并能使用它们来判断图的非平面性； 了解库拉托夫斯基（ Kuratowski）定理和细分图的概念； * 计算机学院 * * 计算机学院 * 第十三章 深刻理解欧拉图和欧拉道路的定义，对于给定的图能判断它是否为欧拉图或存在欧拉道路； 掌握 Fleury 算法并会用 Fleury 算法求出欧拉图中的欧拉回路； 理解中国邮递员问题算法并会用中国邮递员算法求出无向图中的欧拉回路； 深刻理解哈密顿道路及其哈密顿图、图的闭包概念； * 计算机学院 * 会用哈密顿图和含哈密顿道路的充分条件来判断某些图是哈密顿图或是否含有哈密顿道路； 会用破坏哈密顿图的某些必要条件的方法判断某些图不是哈密顿图 严格区分哈密顿图的充分条件和必要条件 理解判断哈密顿图的充分必要条件 了解推销商问题的分枝定界求解方法 * 计算机学院 * 例一 证明当每个结点的度数大于等于 3 时，不存在有 7 条边的连通简单平面图。 证明:(反证法) 设图的边数m=7 由题意，d(Vi) ≥3，Vi为结点 则由握手定理， 则 ∴结点的个数不超过4个，而结点个数为4的完全图的边数为 6, 故应有环或平行边，不是简单连通平面图。 * 计算机学院 * 例二 有 6 个村庄 Vi ， i=l，2，…，6 欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。 * 计算机学院 * * 计算机学院 * 1 3 5 2 7 V2 V6 V4 V1 V3 V5 费用=18 * 计算机学院 * 例三 设图G是具有6个顶结点、12条边的无向简单图, 证明图 G 是哈密顿图。 证明：已知一个图是哈密顿图的充分条件是：图中任意不同两点的度数之和大于等于n。 （反证法）假设图G中存在两个结点v1,v2, 其度数之和不大于等于6, 即 d(v1)+ d(v2) ≤5。 * 计算机学院 * 而删去这两个点后, 至多删去图 G 中的 5 条边。 由于图G是具有6个顶点, 12条边的无向简单图, 删去顶点v1,v2后, 得到的子图为: 具有4个结点, 至少7条边的无向简单图, 但这样的无向简单图不存在(4阶无向简单图最多有6条边), 由此证明图G中任意不同两点的度数之和大于等于6, 图G是哈密顿图。 * 计算机学院 * 1,解：设 L 是叶的数目， m 是树的边数 由握手定理 由树的定义 习题十一 * 计算机学院 * 13、设简单连通图 G=（V，E）的边集 E 恰好可以分划为 G 的两个生成树的边集。证明：如果 G 中恰有两个 4 度以下的结点 u 和 v，则 uv?E。 证：（反证法）设E=E1 ∪ E2 ，E1 ∩ E2= φ T（E1）， T（E2）是 G 的两棵生成树。 如 uv∈E，则 uv∈E1 或 uv∈E2。 不妨设 uv∈E1，由于T（E1）是 G 的生成树， 则 u 或 v 必有其中一个同其它结点相邻，即在T（E1）中，u和v的度数之和大于等于 3. * 计算机学院 * 而在 T（E2）中， u 和 v 分别同其它结点相邻，且相关联的边∈ E2.故在 G 中， d(u)+d(v) ≥ 5. ∵ T（E1）， T（E2）是 G 的两棵生成树 ∴ m（E1）＋m（E2）=2(n-1) 2m(G)=2(m（E1）＋m（E2）)=4(n-1)，由握手定理， 4(n-1) ≥ 4(n-2)+5，矛盾 所以 uv? E 。 * 计算机学院 * 16、证明:在完全二叉树中，边的数目等于 2（t-1），式中t是叶的数目。 证明：设叶结点的个数为t，分支数为 i，边的数目为L， 由定理 11.5 (m-1)i=t-1 ∵ m=2 ∴ i=t-1 由完全二叉树的定义和握手定理， 2L=t