《离散数学 》课件第6-7章 图和树.ppt

*************************************************************************************************************【例6.7.3】设有28盏灯，拟公用一个电源，则至少需要多少个4插头的接线板??解:把28盏灯看成树叶，将4插头的接线板看成分枝点,这样本问题可理解为求一个完全四叉树的分枝点的个数i的问题。由定理7.7.1知，有(4-１)i＝28-1得i＝9所以至少需要9个4插头的接线板。【例6.7.4】8枚硬币问题。若有8枚硬币a，b，c，d，e，f，g，h，其中7枚重量相等，只有1枚稍轻。现要求以天平为工具，用最少的比较次数挑出轻币来。?解:可用图6.7.6所示的树表示判断过程。从图中可知，只需称2次即可挑出轻币。这种用于描述判断过程的树叫判定树。图6.7.66.7.3最优二叉树(optimalbinarytree)定义6.7.6设有一棵二叉树，有ｔ片树叶。使其树叶分别带权w1，w2，…，wt的二叉树称为带权的二叉树。定义6.7.7设有一棵带权w1，w2，…，wt的二叉树,权为wi的树叶的层为Ｌ（wi）。1)该带权二叉树的权W（T）定义为2)在所有带权w1，w2，…，wt的二叉树中，W(T)最小的树称为最优二叉树。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)。【例6.7.5】求带权7，8，9，12，16的最优树。解:全部过程见图6.7.13(a)～(d)。图6.7.13小结：本节介绍了有向树、根树、m叉树、完全m叉树、二叉树、带权树、树的权、最优二叉树等概念及完全m叉树的枝结点数和叶结点数之间的关系、最优二叉树的Huffman算法和二叉树的应用。重点：掌握完全m叉树的枝结点数和叶结点数之间的关系及应用和最优二叉树的Huffman算法。综合练习1.试找出附图的一个真子图、生成子图，并找出它们的补图。2.对于（n，n＋１）图G，证明G至少有一个结点的度数大于等于3。3.证明附图中两个图同构。第1题附图第3题附图综合练习*4.证明任意的9个人中一定有3个人互相认识或者有4个人互相不认识。5.设G是有n个结点的简单图。如果G中每一对结点度数之和大于或等于n－１，那么G是连通图。6.对于任何简单图G，证明或者G是连通的，或者G的补是连通的。综合练习*7.用迪克斯特拉算法求附图中从点a到其它各结点的最短路径，并用图示表示算法中每一次的执行情况。第7题附图综合练习8.已知图G的邻接矩阵如下请画出G的图形。综合练习9.求出附图中有向图的邻接矩阵A，找出从ｖ1到ｖ4长度为2和4的路，用计算A2，A3，A4来验证这一结论。并求出该图的可达性矩阵。第9题附图综合练习10.判断附图中两图是否能一笔画。11.如附图所示，4个村庄下面各有一个防空洞A，B，C，D，相邻的两个防空洞之间有地道相通，