Download presentation
Presentation is loading. Please wait.
1
定义7.5:设图G的顶点非空真子集为V1V, 在G中一个端点在V1中, 另一端点在V(G)-V1中的所有边组成的集合称为G的一个断集或称边割,记为 E(V1(V(G)-V1)), 简记为(V1, V(G)-V1)。 当|(V1, V(G)-V1)|=1时, (V1, V(G)-V1)中的那条边称为割边或 桥。 图 7.2(b) 中边集{e1,e2}和{e1,e2,e3,e4}都是断集(边割)。 割集是断集, 反之不一定。
2
对于连通图G(V,E), 删去一个割集D, 得到两个分支,
顶点集分别为V1和V(G)-V1, 割集D是G中一个端点在V1中, 另一端点在V(G)-V1中的边的全体。 如果在连通图G中, 删去一个断集而不是一个割集, 那么将得到多于两个分支。
3
三、割集与回路 定理7.4：任何一条回路和任何生成树的余树至少有一条公共边。
证明：如果一条回路和一棵生成树的余树没有公共边, 则这回路含在该生成树中, 这是不可能的。 定理7.5：任何一个割集和任何生成树至少有一条公共边。 证明：如果一个割集和一棵生成树没有公共边, 则删去该割集后留下一棵完整的生成树, 也就是说, 删去一个割集后, 不能将图G分为两个分支, 这与割集的定义相矛盾。
4
定理7.6：任何一个回路和任何一个割集有偶数条公共边。
证明：从连通图G中删去一个割集D后, 得到两个顶点子集V1和V2, 考察G中任一条回路C : (1) 如果C中所有顶点在V1(或V2)中, 则C与D没有公共边。 (2)如果C中顶点既有一些在V1中, 又有一些在V2中, 先看D中任何一边, 它的一个端点在V1中, 另一个端点在V2中, 且G中除D中边以外, 不再有任何边连接V1与V2中的顶点。
5
定义7.6：设连通图G中给定生成树T, 对于只包含T中一条枝的割集,称此割集为关于T的基本割集。
因为从生成树T中删去一条枝, 将T分为两棵树, 它将G的顶点集V划分为V1和V-V1, 在G中这两个顶点集之间的连边, 便对应这一枝的唯一的基本割集。
6
设连通图G有e条边, n个顶点, 给定的生成树T应有n-1条枝, 所以恰有n-1个基本割集, 这些基本割集的全体称为生成树T基本割集组。
定义7.7:设连通图G中给定生成树T, 在T中加一条弦, 恰产生一条回路, 称此回路为关于T的基本回路。 由定理 7.1 的等价定义 (4) , 可知在T中加一弦, 产生唯一的回路。 设连通图G有e条边, n个顶点, 给定的生成树应有n-1条枝, e-n+1条弦, 所以恰有e-n+1条基本回路, 这些基本回路的全体称为生成树T的基本回路组。 例如图(a)中给定T={e1,e4,e5,e6}, 关于T的基本割集组: {e1,e2,e8},{e4,e3,e2,e8},{e5,e3, e2, e7}, {e6,e7} 基本回路组: {e2,e1,e4,e5},{e3, e4, e5},{e7,e5,e6},{e8,e1,e4,}
7
7.3最小生成树 定义7.10:设G(V,E,w)是带权连通简单图, w是从E到实数集的函数。又设T是G的一棵生成树,T中所有枝的权之和称为T的权,记为W(T)。具有权 minTW(T)的生成树称为最小生成树。 这个问题是具有实际意义的。例如G的顶点表示城市, G的边表示城市间的道路,边的权表示对应道路的长度, 现在沿着道路架设通讯线路, 将这些城市联系起来, 要求架设的线路最短, 这个问题就是求一棵最小生成树的问题
8
克鲁斯科尔算法的步骤, 通俗地说, 就是先将G中的边按权从小到大顺序排列, 再从小到大依次取出每一边作检查。
一开始取权最小的边{v1,v6}为e1,且w(e1)=l,由e1导出一个部分子图,然后依次每取一边加入已得部分子图。 若保持无回路, 将该边与原有部分子图中边导出一个新的部分子图;若得到回路, 将该边放弃。 上述过程继续进行, 直到所有边均检查完, 得到的部分子图就是所求的一棵最小生成树, 如图(b)所示, 这里e1={v1,v6}和e2={v7,v2}取出后,取e3为{v2,v3},;
9
若改取e3为{v3,v7},可得到另一棵最小生成树
求最小生成树的克鲁斯科尔(Kruskal)算法
10
克鲁斯科尔算法:设G(V,E,w)是有n个顶点的带权连通简单图。
(1)选取G的一边e1,使w(e1)最小,令E1={e1},1i。 (2)若已选Ei={e1,e2,,ei},那么从E-Ei中选取一边ei+1,满足: 1)Ei∪{ei+1}的导出子图中不含有回路; 同时 2)w(ei+1)为满足1)E-Ei中的最小; 3)若ei+1存在,则令Ei+1=Ei∪{ei+1},i+1i,转(2); 若ei+1不存在,则停,此时Ei导出的子图就是所求的最小生成树,记为T。
11
定理7.8:克鲁斯科尔算法所得到的图T是最小生成树。
证明:首先由定理7.1等价定义(4)(T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路)知T是G的一棵子树。 并由等价定义(2)可知边数为n-1(T是无回路图,且e=n-1)，所以为G的生成树。 下面证明T是最小生成树即可。
12
用反证法证明, 假设T不是G的最小生成树,而S是G的生成树, 并且 W(S)<W(T)。
在生成树T中有n-1条边。 按权从小到大的顺序排列为e1,e2,,ek,,en-1。 若ek是不在S中的第一条边, 也就是说e1,e2,,ek-1是S和T的公共边。 现在对S进行变换,在S上加边ek得到一条回路, 记为C ,在C中必有一边e‘S, 但e’T,否则T中有回路,导致矛盾。 但因为e1,e2,,ek-1是S和T的公共边, e‘S,所以e1,e2,,ek-1和e’不构成回路, 根据克鲁斯科尔算法知w(ek)≤w(e')(否则T应选e')。
13
现从S∪ek中删去e‘,得到生成树S’,由于w(ek)≤w(e‘),所以W(S’)≤W(S),并且S‘与T的公共边比S与T的公共边多一条
重复上述过程,每一步作一次树的变换, 使总权数减少, 最后生成树S变换到生成树T,W(T)≤W(S), 与假设 W(S)<W(T)相矛盾。
14
7.5有根树与二分树 定义7.11：有向图在不考虑弧的方向时是一棵树, 称该有向图为有向树。
显然有向树是弱连通的。现在将讨论一类重要的有向树, 即有根树, 定义如下: 定义7.12：若一棵有向树恰有一个顶点的入度为 0 ,其余所有顶点的入度均为1,则称该有向树为有根树。入度为 0 的顶点称为有根树的根。出度为0的顶点称为有根树的树叶。出度非零的顶点称为分枝点或内点。
15
在有根树中,从根v到其余每个顶点有唯一的一条有向路。这一性质由定义 7.12 即可得出。有根树中还有一些专门术语, 现在介绍如下:
定义7.13：设u是有根树的分枝点, 若从u到w有一条弧 (u,w),则称w为u的儿子,或u为w的父亲。若一个顶点有两个儿子, 则称它们为兄弟。若从u到z有一条有向路, 则称z是u的子孙,或称u是z的祖辈。从根到某一顶点v的路长度称为顶点v的层数。从根到树叶的最大层数, 称为有根树的高。
16
如图是有根树, 顶点标号写在圆圈中。顶点 1 是根, 顶点 6, 8, 9, 10, 11, 12 都是树叶, 顶点 1, 2, 3, 4, 5, 7 都是分枝点, 顶点 1 的层数为 0 , 顶点 2, 3的层数为 1 , 顶点 4, 5, 6, 7, 8 的层数为 2 , 顶点 9, 10, 11, 12 的层数为 3 。
17
有根树的概念非常重要, 原因在于它描述了一个离散结构的层次关系, 而层次结构是一种重要的数据结构, 所以有根树结构在相当广泛的领域中有它的应用。有时只要考虑某一层次上某分枝点为根的局部层次关系, 因此引入下面的概念: 定义7.14：设u是有根树T的任一顶点,以u为根,u及其所有子孙所组成的顶点集记为V',u到这些子孙的有向路上所有弧组成的弧集记为E',称T的子图T'(V',E')为以u为根的子树。
18
前面讨论有根树时, 没有考虑同一分枝点连出的弧的次序, 例如图 所示的有根树就是这样, 它们是相同的有根树。但是在计算机科学中的许多具体问题(如编码理论和程序语言等)一定要考虑这种弧的次序。为此,现在引进有序树的概念。
19
定义7.15：有根树的每个分枝点连出的弧(或者有根树的每一个顶点)从左到右用正整数1,2,,i,标上标号,称该有根树为有序树。
在确定树或画树的方式中,这些标号如果清楚的话, 那么标号可以省略。 如下面2个图中的有序树是不同构的, 对应的有根树却相同, 即如上图(a)、(b)所示。 (c)可表示一个人的长子有三个孩子, 次子没有孩子; (d)可表示一个人的长子没有孩子,而次子有三个孩子 。
20
定义7.16:在有序树中,每个分枝点v至多有m个儿子,称该有序树为m分树。如果每个分枝点恰有m个儿子,称该有序树为正则m分树。
在画有序树时,如果规定将一个分枝点的儿子放在它下面, 那么弧的箭头就可以省略, 因为箭头总是朝下的。如前面例子中的图。
21
例:算术表达式a-(b+(c/d)+(e/f))可以用图中的二分树来表示。所有运算对象都处于树叶的位置, 所有运算符处于分枝点的位置。如果将分枝点连出的弧的次序改变一下, 那么所得到的二分树对应的算术表达式也就改变了。
22
定理7.10:在正则二分树中,它的分枝点数i和树叶数t满足:i=t-1。
因此有2i=i+t-1, 所以i=t-1。 类似可证在正则m分树中有(m-1)i=t-1。
23
定理7.11：设T是正则二分树,I表示所有分枝点的路长度之总和,E表示所有树叶的路长度之总和, 则E=I+2i,其中i是分枝点数。
证明：对分枝点数i进行归纳证明,当i=1时E=2,I=0,所以E=I+2i。
24
假设i=k-1时结论成立。 现考察分枝点数i=k的情况,设分枝点v的两个儿子是树叶,删去v连出的边及其儿子,v的路长度为l, 由归纳假设知, 在T'中,E'=I'+2(k-1)。 类似可证在正则m分树中有E=(m-1)I+mi, 具体证明作为习题。
25
7.6最优树 考虑远距离通讯中的一个问题,一篇英文字母组成的短文如何从发送端发出信息, 通过远距离传输送到接收端。
通常的电报是用长度为5的0和1序列来表示英文字母和标点符号的, 这种长度为5的0和1序列组成的集合称为5单位编码。 为了传输一篇短文,将对应的0和1序列组成的信息串发送出去以后, 在接收端就将此信息串划分成长度为 5 的序列, 这样就得到对应的短文。
26
但在一篇短文中每个字母出现的频率是不同的, 如表所示。
例如e,t的频率要比j,z的频率大很多。为了使短文对应的信息串的总长度缩短, 首先要求出现次数多的字母用较短的 0 和 1 序列表示, 出现次数少的字母用较长的 0 和 1 序列表示;
27
其次要求在接收端能从一个信息串中明确地分辨出字母所对应的序列。例如字母 a,b,c,d,e分别用下列 0 和 1 序列表示, 对应关系如下:
把集合{00,110,010,10,01}叫做码。 如果接收端收到信息串是010010, 这时分辨不清发送来的是ead还是cc,这是因为e对应的序列是c对应序列的前缀。 为了避免此情况的发生, 只要将c对应的序列改为111,那么才能确定送来的是ead。 集合{00,110,111,10,01}就叫前缀码。
28
定义7.17：二进制有限序列组成的集合称为码。其中每个元素称为一个码字。在一个码中,任一码字都不是其它码字的前缀, 称该码为二元前缀码,简称前缀码。
为了设计 26 个英文字母所对应的前缀码, 先来看前缀码与二分树的关系。 定理7.12：给定一棵二分树, 则可确定一个前缀码。反之, 对应于一个前缀码, 存在一棵二分树。 证明
29
对于图 7.12 中的前缀码来说, 若我们接收到信息串序列为 , 那么可以从图的二分树树根出发, 依序列的次序, 当遇到 0 时, 就沿着标记为 0 的边走;当遇到 1 时, 就沿着标记为 1 的边走, 一直走至树叶, 这样前缀码中的一个序列就被找到。 然后再回到根, 用同样方法可以找出下一个序列。这样的过程保证使信息串序列总可分割成前缀码中的序列。于是从信息串序列 可以得到对应的英文字母aabe。
33
霍夫曼算法:设n个权w1,w2,,wn,w1w2wn
34
于是得到n-1棵树, 它们的根分别带权w1+w2,wn,
(此时w1+w2w3不一定成立)。再在n-1棵树中找出两棵根带权最小的树, 合并为一棵新的二分树, 使得这两棵树分别是它的左、右子树, 新的二分树的根带的权为原两棵树根带的权之和, 每一步选择两棵根带权最小的树合并为一棵二分树, 重复这一过程直到只有一棵二分树为止。可以证明这棵树是带权w1,w2,,wn的最优树。 例:构造带权 2,4,7,8,10,12 的最优树。构造过程如图所示。
35
这棵最优树的权为:2*4+4*4+7*3+12*2+8*2+10*2=105
一般来说, 带权w1,w2,,wn的最优树不一定是唯一的。
36
作业: P ,12,14,15, 17,18,19,20,21,22
Similar presentations
