离散数学左孝凌第七章.ppt

1952年哈夫曼给出了求带权w1，w2，…，wt的最优树的方法: 令S={w1，w2，…，wt}，w1≤w2≤…≤wt，wi是树叶vi所带的权（i=1，2，…，t）。 （1）在S中选取两个最小的权wi，wj，使它们对应的顶点vi，vj做兄弟，得一分支点vij，令其带权 wij=wi+wj。 （2）从S中去掉wi，wj，再加入wij。 （3）若S中只有一个元素，则停止，否则转到(1)。 【例7.6.5】求带权7，8，9，12，16的最优树。 解:全部过程见图7.6.13(a)～(d)。 第七章 图论  7.6 根树及其应用 图7.6.13 小结：本节介绍了有向树、根树、m叉树、完全 m叉树、二叉树、带权树、树的权、最优 二叉树等概念及完全m叉树的枝结点数和 叶结点数之间的关系和最优二叉树的 Huffman算法。 重点：掌握完全m叉树的枝结点数和叶结点数之间的关系及应用和最优二叉树的Huffman算法。 作业:P337(3),(5a) 第七章 图论  7.6 根树及其应用 习题七 １.试找出附图的一个真子图、生成子图，并找出它们的补图。 ２.对于（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题附图 习题七 (4)证明由第(3)条可推出第(4)条。 若图不连通,则存在两个结点vi和vj,在vi和vj之间没有路,若加边(vi,vj)不会产生简单回路（圈）,但这与假设矛盾。由于T无圈,所以删去任一边,图便不连通。 (5)证明由第(4)条可推出第(5)条。 由连通性知,任两点间有一条路径,于是有一条通路。若此通路不唯一,则T中含有简单回路,删去此回路上任一边,图仍连通,这与假设不符,所以通路是唯一的。 第七章 图论  7.5 树与生成树 (6)证明由第(5)条可推出树的定义。 显然连通。若有圈,则圈上任意两点间有两条通路,此与通路的唯一性矛盾。证毕。 由定理7.5.2所刻画的树的特征可见：在结点数给定的所有图中，树是边数最少的连通图，也是边数最多的无圈图。由此可知，在一个（n，m）图G中，若m＜n－1，则G是不连通的；若m＞n－1，则G必定有圈。 第七章 图论  7.5 树与生成树 【例7.5.2】T是一棵树,有两个2度结点，一个3度结点，三个4度结点，T有几片树叶？ 解：设树T有x片树