离散数学07习题.ppt

第7章 树 王瑞民 iermwang@zzu.edu.cn P124 1(1)画带权1,2,3,4,5,6,7,8,9的最优二元树 Huffman算法求解 P1241(2)画带权1,2,3,4,5,6,7,8,9的最优三元树 P124 2 7个符号在通信中的频率： a:35%,b:20%,c:15%,d:10%,e:10%,f:5%,g:5%,构造2元前缀码，使得出现符号最少 用较短符号传传输频率高的数字 即求权分别为35,20,15,10,10,5,5的最优树 排列为：5,5,10,10,15,20,35 P124 3 6个英文字母对应二元完全树的6片树叶 令b,d,g,o,y,e对应编码分别为000,001,010,011,10,11 {000,001,010,011,10,11}为前缀码 goodbye对应编码信息为 0100110110010001011 P125 1证明：生成树的补集不包含割集，割集的补不包含生成树 证明：设G的生成树T的补为~T=G-T。若~T包含有G的一边割集S，则S?E(~T)，则T?G-S不连通，与T连通矛盾，即生成树的补集不包含割集 设S是G边割集，则~S=G-S，由边割集定义知~S不连通，而G的任何生成树T是连通的，故~S不能包含G的任何生成树 2题准备(1) 一个边割集与基本回路都有偶数条公共边 证明：删除割边集中的所有边，则G分成互不连通的G1和G2 G1与G2间连通的边都在边割集中 从任一顶点出发又回到自身的回路必然在G1和G2之间来回偶数次(来回次数为0，表示此回路的所有顶点都在G1和G2中)，故，此回路与边割集有偶数条公共边 2题准备(2) 对给定的一棵生成树T，设D={e1,e2,…,ek}是边割集，其中e1是T树枝，e2,e3,…,ek是T的弦，则e1包含在与ei(2?i?k)对应的基本回路中 证明：设C是对应于弦e2的基本回路 因为e2在回路C中，也在D中，由(1)知 C与D有偶数公共边，由于C中只有一条弦e2，C与D的公共边只能是树枝，故只可能是e1为公共边，对应于e3,e4,…,ek的基本回路也包含e1 另外：设C’是对应于不在D中的任何弦的基本回路，C’不包含e1。否则C‘与D也有一条公共边e1 P125 2 证明：设边a在T1中，a是T1的树枝，通过树枝a有一边割集D 边a不在T2中，a是T2的弦，存在对应于边a的基本回路C，边割集D与回路C有公共边a，由(1)知，C与D至少有一公共边b b在基本回路C中，b是T2的树枝，又b在边割集D中，b不是T1的树枝 在树T2中，删除b，加上a，得到图G的一棵生成树，(T2-{b})U{a}是图G的一棵生成树 因b在在边割集D中，边a是D中的树枝，由(2)知，a包含在对应边b的基本回路中，删除边a添加边b， (T2-{a})U{b}也是图G的一棵生成树 P125 3 证明：作一棵以b为树枝，a为弦的生成树T L={a,b,…}是包含且仅包含一条弦a的基本回路 过b的边割集C={b,…}且C中包含且仅包含一个树枝b 由准备(1)知，基本回路与边割集有偶数条公共边，b是其中一条公共边，必有另一条公共边，由C知，一定是弦 而L中只有a是弦，故L?C={a,b} P125 4 证明：设G是无向简单连通图，对任何边e 若e不在任何回路中，则e必定属于一棵生成树。否则，G-e不连通，不包含e的生成树，当然也不连通 若e在某一回路C中，设C={v1,e1,v2,e2,…,vi,ei,vi+1,…,ek,v1}，且e=ei(vi,vi+1)，删去C中e之外的任何一边，得到的子图连通，所得到的图为生成树，并且包含e P125 5 ?)设e在G的每棵生成树中，但e不是G的割边，则G-e连通，由定理7.4.1知，G-e有一棵生成树T，T也是G的生成树且不包含e，与e在G的每棵生成树中矛盾 ?)设e是G割边，但G存在一棵生成树T不包含e，由定理7.4.2知，T+e产生一个唯一的回路，与e是G的割边矛盾，故e在G的每棵生成树中 P129 分别使用Prim和Kruskal算法 略 第8章 p134 1 解：v2,v1,7,2,8,9,12,11,10,12,6,5,10,3,4,5,3,2,10,9,2 2解：n为大于n的奇数时，Kn的每个顶点度数为偶数，存在欧拉回路 P134 3 (1)解:添加一边只能使得两个顶点的度数改变奇偶性，k个奇数度的顶点，至少添加k/2条边才能使得k个奇数度顶点度数变为偶数，从而得到一条偶拉回路 (2)证明:图G中奇数度顶点数目为偶数，故k是偶数 将G中k个奇数度顶点分为数目相等的两个组{u1,u2,…,uk/2}，{v1,v2,…,vk/2} P134 3 (2)证明续:在图G中添加边(u1,v1),…,(uk/2,v