《离散数学》ppt课件

1、离散数学离散数学Discrete Discrete Mathematics Mathematics 16.1 无向树及其性质无向树及其性质16.2 生成树生成树16.3 根树及其运用根树及其运用定义定义16.1无向树无向树: 连通无回路的无向图连通无回路的无向图平凡树平凡树: 平凡图平凡图森林森林: 每个连通分支都是树的非连通的无向图每个连通分支都是树的非连通的无向图树叶树叶: 树中度数为树中度数为1的顶点的顶点分支点分支点: 树中度数树中度数2的顶点的顶点右图为一棵右图为一棵12阶树阶树.声明声明:本章中所讨论的回路均本章中所讨论的回路均 指简单回路或初级回路指简单回路或初级回路定理定理16

2、.1 设设G=是是n阶阶m条边的无向图，那么以下等价的：条边的无向图，那么以下等价的：1G是树是树;2G中恣意两个顶点之间存在独一的途径中恣意两个顶点之间存在独一的途径;3G中无回路且中无回路且m=n1;4G是连通的且是连通的且m=n1;5G是连通的且是连通的且G中任何边均为桥中任何边均为桥;6G中没有回路中没有回路, 但在任何两个不同的顶点之间加一条新边后但在任何两个不同的顶点之间加一条新边后所得图中有独一的一个含新边的圈所得图中有独一的一个含新边的圈. 证明：证明： 由于由于G是树，所以是树，所以G是连通的，是连通的，u, vV，u和和v之间存在一条路。之间存在一条路。假设路不独一，设假设

3、路不独一，设L1和和L2都是都是u和和v之间的路，之间的路，那么由那么由L1和和L2上的边组成了上的边组成了G中的一个回路，矛盾。中的一个回路，矛盾。 先证先证G中无回路。假设中无回路。假设G中存在某个结点中存在某个结点v上的环，上的环， uV，由条件知，由条件知u到到v存在一条路存在一条路L1：uv， 那么那么u到到v有另一条路有另一条路L2：uvv，矛盾。，矛盾。 假设假设G中存在长度大于等于中存在长度大于等于2的一条回路，那么回路上两个结点之的一条回路，那么回路上两个结点之间存在不同的路间存在不同的路, 矛盾。所以矛盾。所以G中无回路。中无回路。 以下用归纳法证明以下用归纳法证明m=n1

4、。 当当n=1时，时，G为平凡图，为平凡图，m=0=11=n1。结论成立。结论成立。 设设nk时，结论成立。下证时，结论成立。下证n=k+1时，结论也成立。时，结论也成立。 设设e=(u,v)是是G中的一条边，由于中的一条边，由于G中无回路，所以中无回路，所以G-e有两个有两个连通分支连通分支G1和和G2，设它们的结点数和边数分别为：，设它们的结点数和边数分别为：n1，m1和和n2，m2。 于是有于是有n1k和和n2k，由归纳假设知：，由归纳假设知：m1=n11和和m2=n2-1， m=m1m21=n1-1n2-11=n-1。只须证明只须证明G是连通的。假设不然是连通的。假设不然,设设G有有s

5、(s2)个连通分支个连通分支G1,G2,Gs, Gi中均无回路，都是树。由中均无回路，都是树。由可知，可知，mi=ni1，i=1,s。于是于是m=m1m2ms=n1-1n2-1ns-1=n1n2ns-s=ns，由于由于s2，这与，这与m=n1矛盾。所以矛盾。所以G是连通图。是连通图。 只须证明只须证明G的每一条边均为桥。的每一条边均为桥。设设e是是G的恣意边，删除的恣意边，删除e得子图得子图G1，它的边数，它的边数m1=m-1，结点数，结点数n1=n， m1=m1=n-1-1=n-2=n1-2n1-1，由习题，由习题14的第的第49题知题知G1不是连通图，不是连通图，所以所以e是桥。是桥。 由

6、于由于G中每一条边均为桥，因此中每一条边均为桥，因此G中无回路。又由于中无回路。又由于G连通，所以连通，所以G是树。由是树。由知，知，u, vV，uv，u与与v之间存在一条独一的路。之间存在一条独一的路。在在u与与v之间添加一条新边之间添加一条新边, 得到得到G的一条回路的一条回路, 显然这条回路是独一的。显然这条回路是独一的。 只须证明只须证明G是连通的，是连通的，u, vV，uv，在，在u与与v之间添加一条新边之间添加一条新边(u,v)就产生就产生G的一个独一的回路，故结点的一个独一的回路，故结点u和结点和结点v连通。由于连通。由于u与与v是恣意是恣意的，所以的，所以G是连通图。是连通图。

7、 )(2)()1(2xnxvdni 定理定理16.2 设设T 是是 n 阶非平凡的无向树，那么阶非平凡的无向树，那么T中至少有两片中至少有两片树叶树叶. 由上式解出由上式解出x2.证证 设设T有有x片树叶，由握手定理及定理片树叶，由握手定理及定理9.1可知，可知，例例1 知无向树知无向树T中中, 有有1个个3度顶点度顶点, 2个个2度顶点度顶点, 其他顶点全是其他顶点全是树叶树叶. 试求树叶数试求树叶数, 并画出满足要求的非同构的无向树并画出满足要求的非同构的无向树. 解解 用树的性质用树的性质m=n1和握手定理和握手定理. 设有设有x片树叶，于是片树叶，于是 n=1+2+x=3+x, 2m=

8、2(n1)=2(2+x)=13+22+x解出解出x=3，故，故T有有3片树叶片树叶. T的度数列为的度数列为1, 1, 1, 2, 2, 3 有有2棵非同构的无向树棵非同构的无向树, 如下图如下图例例2 知无向树知无向树T有有5片树叶片树叶, 2度与度与3度顶点各度顶点各1个个, 其他顶点的度数其他顶点的度数均为均为4. 求求T的阶数的阶数n, 并画出满足要求的一切非同构的无向树并画出满足要求的一切非同构的无向树. 解解 设设T的阶数为的阶数为n, 那么边数为那么边数为n1, 4度顶点的个数为度顶点的个数为n7. 由由握手定理得握手定理得 2m=2(n1)=51+21+31+4(n7)解出解出

9、n=8, 4度顶点为度顶点为1个个. T的度数列为的度数列为1,1,1,1,1,2,3,4 有有3棵非同构的无向树棵非同构的无向树 定义定义16.2 设设G为无向连通图为无向连通图G的生成树的生成树: G的生成子图并且是树的生成子图并且是树生成树生成树T的树枝的树枝: G在在T中的边中的边生成树生成树T的弦的弦: G不在不在T中的边中的边T留意：留意： 不一定连通不一定连通, 也不一定不含回路也不一定不含回路.T生成树生成树T的余树的余树 : 一切弦的集合的导出子图一切弦的集合的导出子图例例e1e2e7e8e9e11e10e3e5e4e6(1)(2)生成树生成树T的弦的弦: e6, e7, e

10、8, e10 , e11定理定理16.3无向图无向图G具有生成树当且仅当具有生成树当且仅当G为连通图。为连通图。证明：必要行显然。证明：必要行显然。以下证明假设无向图以下证明假设无向图G为连通图，那么为连通图，那么G具有生成树。具有生成树。假设连通图假设连通图G无回路，那么无回路，那么G本身就是一棵生成树；本身就是一棵生成树；假设假设G至少有一个回路，删除此回路的一边，得到子图至少有一个回路，删除此回路的一边，得到子图G1，它依然，它依然连通，并与连通，并与G有一样结点集。有一样结点集。假设假设G1无回路，那么无回路，那么G1就是一棵生成树；就是一棵生成树；假设假设G1仍有一个回路，再删除仍有

11、一个回路，再删除G1回路上的一边。回路上的一边。反复上述过程反复上述过程,直至得到一个无回路的连通图直至得到一个无回路的连通图, 该图就是一棵生成树该图就是一棵生成树.推论推论3 设设 为为G的生成树的生成树 T 的余树，的余树，C 为为G 中恣意一个圈，那么中恣意一个圈，那么C与与 一定有公共边一定有公共边. TT推论推论1 设设n阶无向连通图有阶无向连通图有m条边条边, 那么那么mn1. 推论推论2 设设n阶无向连通图有阶无向连通图有m条边条边, 那么它的生成树的余树有那么它的生成树的余树有mn+1条边条边.定义定义16.3 设设T是是n阶阶m条边的无向连通图条边的无向连通图G的一棵生成树

12、的一棵生成树,设设e1, e2, , emn+1为为T的弦的弦. 设设Cr为为T添加弦添加弦er产生的产生的G中独一的中独一的圈圈, 称称Cr为对应弦为对应弦er的根本回路或根本圈的根本回路或根本圈, r=1, 2, mn+1. 称称C1, C2, , Cmn+1为对应为对应T的根本回路系统的根本回路系统. mn1称为称为G的圈的圈秩秩.无向连通图的秩，与生成树的选择无关。无向连通图的秩，与生成树的选择无关。求根本回路的算法求根本回路的算法: 设弦设弦e=(u,v), 先求先求T中中u到到v的途径的途径 uv, 再并上弦再并上弦e, 即得对应即得对应e的根本回路的根本回路. 例例e1e2e7e

13、8e9e11e10e3e5e4e6生成树生成树T的弦的弦: e6, e7, e8, e10 , e11它们对应的根本回路分别为它们对应的根本回路分别为: C1=e6e4e5 C2=e7e2e1C3=e8e9e2e1 C4=e10e3e5e2C4=e11e3e5e2e9上图的圈秩为上图的圈秩为5,根本回路系统为根本回路系统为C1,C2, C3,C4,C5.定义定义16.5 设设T是是n阶连通图阶连通图G的一棵生成树的一棵生成树, e1, e2, , en1为为T的树枝，的树枝，Si是是G的只含树枝的只含树枝ei, 其他边都是弦的割集其他边都是弦的割集, 称称Si为对应生为对应生成树成树T由树枝由

14、树枝ei生成的根本割集生成的根本割集, i=1, 2, , n1. 称称S1, S2, , Sn1为对应为对应T的根本割集系统的根本割集系统.称称n1为为G的割集秩的割集秩. 求根本割集的算法求根本割集的算法: 设设e为生成树为生成树T的树枝的树枝, Te由两棵子树由两棵子树T1与与T2组成组成, 令令 Se=e | eE(G)且且e的两个端点分别属于的两个端点分别属于T1与与T2 那么那么Se为为e对应的根本割集对应的根本割集. 例例e1e2e7e8e9e11e10e3e5e4e6T的树枝的树枝: e1, e2, e3, e4, e5, e9它们的根本割集分别为它们的根本割集分别为:S1 =

15、e1, e7, e8, S2 =e2, e7, e8 , e10, e11, S3 =e3, e10, e11, S4 =e4, e6, S5 =e5, e6, e10, e11, S9 =e9, e8 , e11 .G的割集秩为的割集秩为6.例例 图中红边为一棵生成树图中红边为一棵生成树, , 求对应它的根本回路系统求对应它的根本回路系统 与根本割集系统与根本割集系统解解 弦弦e,f,ge,f,g对应的根本回路分别为对应的根本回路分别为 Ce=e b c, Cf=f a b c, Cg=g a b c d, Ce=e b c, Cf=f a b c, Cg=g a b c d, C C基基=

16、Ce, Cf, Cg. =Ce, Cf, Cg. 树枝树枝a,b,c,da,b,c,d对应的根本割集分别为对应的根本割集分别为 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, S S基基=Sa, Sb, Sc, Sd.=Sa, Sb, Sc, Sd.定义定义16.4 对无向图或有向图的每一条边对无向图或有向图的每一条边e附加一个实数附加一个实数w(e), 称作边称作边e的权的权. 图连同附加在边上的权称作带权图图连同附加在边上的权称作带权图,

17、记作记作G=. 设设G是是G的子图的子图, G一切边的权的和称作一切边的权的和称作G的权的权, 记作记作W(G). 最小生成树最小生成树: 带权图权最小的生成树带权图权最小的生成树求最小生成树的算法求最小生成树的算法避圈法避圈法 (Kruskal)设设G=, 将非环边按权从小到大排序：将非环边按权从小到大排序：e1, e2, , em.(1) 取取e1在在T中中(2) 检查检查e2, 假设假设e2与与e1不构成回路不构成回路, 那么将那么将e2参与参与T中中, 否那否那么弃去么弃去e2.(3) 检查检查e3, 反复进展直至得到生成树为止反复进展直至得到生成树为止. 例例 求图的一棵最小生成树求

18、图的一棵最小生成树 W(T)=38有向树有向树根树、树根、树叶、内点、分支点根树、树根、树叶、内点、分支点家族树、根子树、有序树家族树、根子树、有序树r叉树叉树r叉有序树叉有序树r叉正那么树叉正那么树r叉有序正那么树叉有序正那么树r叉完全正那么树叉完全正那么树r叉有序完全正那么树叉有序完全正那么树最优最优2叉树与叉树与Huffman算法算法前缀吗与最正确前缀吗前缀吗与最正确前缀吗中序行遍法、前序行遍法、后续行遍法中序行遍法、前序行遍法、后续行遍法波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法 有向树有向树: 基图为无向树的有向图基图为无向树的有向图定义定义16.6 根树根树: 有一个顶点入度

19、为有一个顶点入度为0, 其他的入度均为其他的入度均为1的非平凡的有向树的非平凡的有向树树根树根: 有向树中入度为有向树中入度为0的顶点的顶点树叶树叶: 有向树中入度为有向树中入度为1, 出度为出度为0的顶点的顶点内点内点: 有向树中入度为有向树中入度为1, 出度大于出度大于0的顶点的顶点分支点分支点: 树根与内点的总称树根与内点的总称顶点顶点v的层数的层数: 从树根到从树根到v的通路长度的通路长度树高树高: 有向树中顶点的最大层数有向树中顶点的最大层数根树的画法根树的画法: :树根放上方树根放上方, ,省去一切有向边上的箭头省去一切有向边上的箭头如右图所示如右图所示 a a是树根是树根 b,e

20、,f,h,i b,e,f,h,i是树叶是树叶 c,d,g c,d,g是内点是内点 a,c,d,g a,c,d,g是分支点是分支点 a a为为0 0层层;1;1层有层有b,c; 2b,c; 2层有层有d,e,f;d,e,f; 3 3层有层有g,h; 4g,h; 4层有层有i.i. 树高为树高为4 4定义定义16.7 根树看作一棵家族树根树看作一棵家族树:(1) 假设顶点假设顶点 a 邻接到顶点邻接到顶点 b, 那么称那么称 b 是是 a 的儿子的儿子, a 是是 b 的父亲的父亲;(2) 假设假设b和和c为同一个顶点的儿子为同一个顶点的儿子, 那么称那么称b和和c是兄弟是兄弟;(3) 假设假设a

21、b且且a可达可达b, 那么称那么称a是是b的祖先的祖先, b是是a的后代的后代.有序树有序树: 将根树同层上的顶点规定次序将根树同层上的顶点规定次序r叉树叉树:根树的每个分支点至多有根树的每个分支点至多有r个儿子个儿子r叉正那么树叉正那么树: 根树的每个分支点恰有根树的每个分支点恰有r个儿子个儿子r叉完全正那么树叉完全正那么树: 树叶层数一样的树叶层数一样的r元正那么树元正那么树r叉有序树叉有序树: 有序的有序的r元树元树r叉正那么有序树叉正那么有序树: 有序的有序的r元正那么树元正那么树r叉完全正那么有序树叉完全正那么有序树: 有序的有序的r元完全正那么树元完全正那么树)()(1itiivl

22、wtW 定义定义16.9 设设2叉树叉树T有有t片树叶片树叶v1, v2, , vt, 树叶的权分别树叶的权分别 为为w1, w2, , wt, 称称 为为T的权的权, 记作记作 W(T), 其中其中l(vi)是是vi的层数的层数. 在一切有在一切有t片树叶片树叶, 带权带权 w1, w2, , wt 的的 2元元树中树中, 权最小的权最小的2叉树称为最优叉树称为最优 2叉树叉树.定义定义16.8 设设v为根树的一个顶点且不是树根为根树的一个顶点且不是树根, 称称v及其一切后代及其一切后代的导出子图为以的导出子图为以v为根的根子树为根的根子树. 2叉正那么有序树的每个分支点的两个儿子导出的根子

23、树分叉正那么有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树别称为左子树和右子树.例子例子:P313 图图16.7以下图中的三棵树以下图中的三棵树T1，T2和和T3都是带权都是带权2，2，3，3，5的二叉树的二叉树.以上三棵树不是最优树。以上三棵树不是最优树。W(T1)=2222335332=38W(T2)=3454332221=47W(T3)=3333522222=36它们的权分别是：它们的权分别是： Huffman算法算法:给定给定t片树叶的权为片树叶的权为W1,W2,Wt且且W1W2Wt。 衔接权为衔接权为W1，W2的两片树叶，得一分枝点，其权为的两片树叶，得一分枝点，其权

24、为W1W2在在W1W2，W3，Wt中选出两个最小的权，衔接它们对中选出两个最小的权，衔接它们对应的结点应的结点(不一定是树叶不一定是树叶)，得新分枝点及所带的权，得新分枝点及所带的权反复，直到构成反复，直到构成t1个分枝点，个分枝点，t片树叶为止片树叶为止例例16.4 求带权求带权2，2，3，3，5的最优二叉树的最优二叉树T。 解：生成最优二叉树的过程解：生成最优二叉树的过程最优树的权为：最优树的权为：W(T)=2323523232=34例例 求带权为求带权为1, 1, 2, 3, 4, 5的最优树的最优树. 解题过程由以下图给出解题过程由以下图给出W(T)=38定义定义16.10 设设 =1

25、2n-1n是长度为是长度为n的符号串的符号串的前缀的前缀: 12k , k=1,2,n-1 前缀码前缀码: 1, 2, , m, 其中其中1, 2, , m为非空字为非空字符串符串, 且任何两个互不为前缀且任何两个互不为前缀2元前缀码元前缀码: 只出现两个符号只出现两个符号(如如0与与1)的前缀码的前缀码(2) 0,10,110, 1111, 10,01,001,110是前缀码是前缀码 0,10,010, 1010 不是前缀码不是前缀码例如例如(1) 1,00,011,0101,01001,01000是前缀码。而是前缀码。而 1,00,0101,0100,01001,01000不是前缀码不是前

26、缀码一棵一棵2元树产生一个二元前缀码元树产生一个二元前缀码:对每个分支点对每个分支点, 假设关联假设关联2条边条边, 那么给左边标那么给左边标0, 右边标右边标1; 假设只关联假设只关联1条边条边, 那么可以给它标那么可以给它标0(左左), 也可以标也可以标1(右右). 将从树根到每一片树叶的通路上标的数字组成的字符串记在将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处树叶处, 所得的字符串构成一个前缀码所得的字符串构成一个前缀码.如右图所示如右图所示定理定理16.6 由一棵给定的二叉正那么树，可以产生独一的二元前缀由一棵给定的二叉正那么树，可以产生独一的二元前缀码码.例例16.5求

27、以下图所示的二叉树产生的前缀码。求以下图所示的二叉树产生的前缀码。产生的前缀码为：产生的前缀码为：01,11,000,0010,0011 例例 在通讯中，设八进制数字出现的频率如下：在通讯中，设八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%采用采用2元前缀码元前缀码, 求传输数字最少的求传输数字最少的2元前缀码元前缀码 (称作最正确称作最正确前前缀码缀码), 并求传输并求传输10n(n2)个按上述比例出现的八进制数字个按上述比例出现的八进制数字需需要多少个二进制数字？假设用等长的要多少个二进制数字？假设用等长的 (长为长为

28、3) 的码字传输需的码字传输需求求多少个二进制数字多少个二进制数字?解解 用用Huffman算法求以频率算法求以频率(乘以乘以100)为权的最优为权的最优2元树元树. 这这里里 w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 最优最优2元树如下图元树如下图. 编码编码: 0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-00001传传100个按比例出现的八进制数字所需二进制数字的个数为个按比例出现的八进制数字所需二进制数字的个数为 W(T)=285.传传10n(n2)个所用二进制数字的个数为个所用二进制数字的个数为2.8510n, 而用等长码而用等长码(长为长为3)需求用需求用 310n