左孝凌离散数学课件7.ppt

【例7.6.5】求带权7， 8， 9， 12， 16的最优树。 解: 全部过程见图7.6.13(a)～(d)。 图7.6.13 小结：本节介绍了有向树、根树、m叉树、完全 m叉树、二叉树、带权树、树的权、最优 二叉树等概念及完全m叉树的枝结点数和 叶结点数之间的关系和最优二叉树的 Huffman算法。 重点：掌握完全m叉树的枝结点数和叶结点数之间的关系及应用和最优二叉树的Huffman算法。 作业: P337 (3),(5a) 习 题 七 １. 试找出附图的一个真子图、 生成子图， 并找出它们的补图。 ２. 对于（n， n＋１）图G， 证明G至少有一个结点的度数大于等于３。 ３. 证明附图中两个图同构。 第 1 题 附图 第 ３ 题 附图 *４. 证明任意的９个人中一定有３个人互相认识或者有 ４个人互相不认识。 ５. 给定图G（见附图）， 求 1) 从A到F的所有通路。 2) 从A到F的所有迹。 3) A和F之间的距离。 4) 指出图G中所有的圈。 第 ５ 题 附图 ６. 设G是有n个结点的简单图。 如果G中每一对结点度数之和大于或等于n－１， 那么G是连通图。 ７. 对于任何简单图G， 证明或者G是连通的， 或者G的补G 是连通的。 *８. n个城市由k条公路网连接（一条公路定义为两个城市间的一条道路， 并且它们之间不能通过任何中间城市）。 证明： 如果有 则人们总能通过连接的公路， 在任何两个城市之间旅行。 *９. 用迪克斯特拉算法求附图中从点ａ到其它各结点的最短路径， 并用图示表示算法中每一次的执行情况。 第 ９ 题 附图 10. 已知图G的邻接矩阵如下 请画出G的图形。 11. 求出附图中有向图的邻接矩阵A， 找出从ｖ1到ｖ4长度为２和４的路， 用计算A2， A3， A4来验证这一结论。 并求出该图的可达性矩阵。 12. 求证： 在任意一个有向图中， 所有结点的入度之和等于它们的出度之和。 13. 试求出附图中所有的强分图、 弱分图和单向分图。 第 11 题 附图 第 13 题 附图 14. 判断附图中两图是否能一笔画。 15. 如附图所示， ４个村庄下面各有一个防空洞A， B， Ｃ， D， 相邻的两个防空洞之间有地道相通， 并且每个防空洞各有一条地道与地面相通。 能否安排一条路线， 使得每条地道恰好走过一次， 既无重复也无遗漏？ 第 14 题 附图 第 15 题 附图( 表示地道) 16. 画一个图， 1) 使它有一条欧拉回路和一条汉密尔顿回路。 2) 使它有一条欧拉回路但没有汉密尔顿回路。 3) 使它没有欧拉回路但有汉密尔顿回路。 4) 使它既没有欧拉回路也没有汉密尔顿回路。 17. 附图中的图G是否是汉密尔顿图。 第 17 题 附图 18. 完全图Kn是否是欧拉图， 是否是汉密尔顿图。 19. 设G是一个具有n个结点的简单无向图（n≥３）， G的结点表示人， G的边表示他们间的友好关系， 若两个结点被一条边连接， 当且仅当对应的人是朋友。 1) 一个结点的度数可作何解释？ 2) 对G是连通图这一事实应作何解释？ 3) 对G是汉密尔顿图又可作何解释？ 第 20 题 附图 第 21 题 附图 (6) 证明由第(5)条可推出树的定义。 显然连通。若有圈,则圈上任意两点间有两条通路,此与通路的唯一性矛盾。证毕。 由定理7.5.2所刻画的树的特征可见： 在结点数给定的所有图中， 树是边数最少的连通图， 也是边数最多的无圈图。 由此可知， 在一个（n， m）图G中， 若m＜n－1， 则G是不连通的； 若m＞n－1， 则G必定有圈。 【例7.5.2】T是一棵树,有两个2度结点，一