《离散数学 》课件_第8章.ppt

例8.8-6算术表达式a-b+(c/d+e/f)可用图8.8―10表

达。注意所有运算对象都处于树叶位置,运算符处于分枝点位置,括号不表示,计算次序按路径长度远的先算。图8.8―108.8.2前缀码和最优树通信中,我们常用5位0、1序列表示一个英文字母(因为26＜25)。在接收端每收到5位0、1序列就可确定一个字母。但各字母被使用的次数是不均匀的,例如e,t用得频繁,q和z用得稀少。于是人们希望用较短序列去表示使用频繁的字母,用较长的序列去表示用得稀少的字母,这样就可缩短信息串的总长。但是产生了一个问题:当我们用不同长度的序列去表示字母时,在接收端的人如何将一长串的0和1明确无误地分割成字母对应的序列呢?譬如,我们用00表示e,用01表示t,用0001表示q,那么当接收端收到信息串0001时,我们将不能决定传递的内容是et还是q?现在让我们用完全二元树来解决这个编码问题。

在一棵完全二元树中,我们把每一结点的引出左枝记上0,右枝记上1,把从根到每一片树叶所经过的边的记号串作为这片叶子的标记。这些标记的集合称为前缀码,如图8.8―11中所示的{000,001,01,10,11},因为在这集合中,没有一个序列是另一序列的前缀。容易看出一个前缀码和一棵完全二元树是一一对应的。定理8.7―8对给定的一棵生成树,设C={e1,e2,…,ek}是一条基本回路,其中e1是弦,e2,…,ek是生成树的枝,则e1包含在对应于ei(i=2,…,k)的基本割集中,而不包含在任何其它的基本割集中。8.7.3最小生成树设图G=〈V,E,W〉是赋权连通简单无向图,W是E到非负实数的函数,边〈i,j〉的权记为W(i,j)。若T是G的生成树,T中树枝的权之和称为T的权,记为。所有生成树中具有最小权的生成树称为最小生成树。求最小生成树是下列一类实际问题的数学抽象,例如“为了把若干城市联结起来,要求设计最短通信线路”,“为了解决若干居民点供水,要求设计最短的自来水管线路”等,本小节将介绍在给定的一个赋权连通图中寻求最小生成树的有效算法。定理8.7―9设G是边权全不相同的连通简单图,C

是一条简单回路,则C上权最大的边e必定不在G的最小生成树中。证用反证法。设e在最小生成树T中,包含e的基本割集为D。C和D有偶数条共同边,其中一条为e,另一条为弦f,将边f加到T上,得到一生成子图,崐记为H,它恰包含一条基本回路,记为Cf,根据定理8.7―7,e也含在基本回路Cf中。于是从H中删去边e,便可以得到一棵新的生成树,它的权小于T的权,与T是最小生成树矛盾。证毕。在这个定理的基础上,建立了克鲁斯克尔(Kruskal)算法:设G有n个顶点,m条边,先将G中所有的边按权的大小次序进行排列,不妨设W(e1)＜W(e2)＜…＜W(em)(1)k←1,A←。(2)若A∪{ek}导出的子图中不包含简单回路,则A←A∪{ek}。(3)若A中已有n-1条边,则算法终止,否则k←k+1,转至(2)。以上算法是正确的,理由如下:(1)由边集A所导出的子图T是图G的生成树。因为根据算法而得到的子图T是在n个顶点上有n-1条边且无简单回路的图。根据定理8.7―1第1条,它是树,另外T包含了图G的全部顶点,所以T是G的生成树。(2)T是最小生成树。用反证法。假设T′是最小生成树而不是T,则存在一条边ei∈T′,但eiT,将ei加到T得到一基本回路C,由上述算法知,ei是C中的权最大的边,否则不会排除出T,但根据定理8.7―9,C中的权最大的边ei不应在最小生成树T′中,这与ei∈T′矛盾。所以T是最小生成树。图8.7―5给出了求最小生成树的例子,要注意带权4和7的边是怎样在一步一步作图的过程中被排除掉。以上算法中假设G中的权全不相同,实际上,这种算法完全适用于边权任意情况。只是所求得之最小生成树不唯一。?图8.7―58.8.1有向树的定义和性质定义8