数据结构-树_ou

1、1847年德国物理学家柯希霍夫年德国物理学家柯希霍夫(Kirchhof)提出了树的提出了树的概念概念.即所谓无圈连通图即所谓无圈连通图,他是在研究电路网络时考虑电他是在研究电路网络时考虑电路网的所谓路网的所谓“生成树生成树”,即一个含有电路图上所有节点即一个含有电路图上所有节点的树形子图的树形子图.1857年英国数学家凯莱年英国数学家凯莱(Caylay Arthur)研究碳氢化研究碳氢化合物时合物时,提出了树的概念与记数的理论提出了树的概念与记数的理论.1889年凯莱给出了完全图年凯莱给出了完全图Kn的概念的概念.例如例如10个顶点的个顶点的完全图竟有一亿棵生成树完全图竟有一亿棵生成树.195

2、6年年Kruskal设计了求最优树的有效算法设计了求最优树的有效算法.树是一类既简单而又非常重要的图，是计算机中一种树是一类既简单而又非常重要的图，是计算机中一种基本的数据结构和表示方法，在输电网络分析设计、基本的数据结构和表示方法，在输电网络分析设计、有机化学、最短连接及渠道设计等领域也都有广泛的有机化学、最短连接及渠道设计等领域也都有广泛的应用。应用。定义定义4.2.1 设设G=( (P, ,L)是图。如果是图。如果G是连通的是连通的, ,并且无回路，并且无回路，则称则称G为树。为树。无回路的图无回路的图( (可能不连通可能不连通) )也称为森林。也称为森林。 例：例：引理引理4.2.1设

3、设G是至少有一条边的有限图，且无是至少有一条边的有限图，且无回路，则回路，则G至少有一个点只相邻于另一个点，即至少有一个点只相邻于另一个点，即G至少有一个点度数为至少有一个点度数为1。 证明：证明：因为因为G至少有一条边至少有一条边,所以所以,G有一点有一点v1，且且v1有相邻点有相邻点v2。若。若v2即为所求，则引理得证。即为所求，则引理得证。 否则否则, ,令令v3为为v2的不同于的不同于v1相邻点相邻点, ,以此类推，以此类推，即，对即，对k 2，或者，或者vk只与只与vk-1相邻，从而相邻，从而vk即为所即为所求；或者求；或者vk又相邻于又相邻于vk+1 vk-1。于是得。于是得v1,

4、 ,v2, , ,vk-1, ,vk, ,vk+1, , ,因为因为G无回路，故这一无回路，故这一串点不能有重复。又因为串点不能有重复。又因为G有限，故上述过程必有限，故上述过程必在有限步内停止。从而引理得证。在有限步内停止。从而引理得证。 1)2)；反证，；反证，若若G删去边删去边vv后是连通的，后是连通的，则有从则有从v到到v的路的路(v,v1,v)，不妨设这是从，不妨设这是从v到到v的所有路中最短者，于是，这是一条简的所有路中最短者，于是，这是一条简单路。显然，此路长度不小于单路。显然，此路长度不小于2，（，（因为因为长度长度为为1的只有的只有vv,而现在假设而现在假设vv已经被删除了已

5、经被删除了,且且图图G中没有第二个中没有第二个vv）。）。于是这条路再加上边于是这条路再加上边vv就是就是G中一条回路中一条回路,矛盾矛盾 2)3)；因为因为G连通，所以对于连通，所以对于v,v,有从有从v到到v的路，取其最短的路，取其最短者，得从者，得从v到到v的简单路。的简单路。 反证反证，若有两条这样的路，若有两条这样的路， 设为设为 (v0,v1,vn,vn+1)，(v0,v1,vm, vm+1)， 其中其中v0 = v0 =v，vn+1=vm+1=v。 从左向右看可找到最小的从左向右看可找到最小的k，使得，使得vk vk。 于是，从于是，从G删去边删去边vk-1vk，从，从vk-1到

6、到vk还有路还有路 (vk-1,vk, vm+1,vn,vn-1,vk)。 故故G删去边删去边vk-1vk后，所得之图仍连通，矛盾。后，所得之图仍连通，矛盾。 3)1)；由已知条件知，由已知条件知，G是连通的。是连通的。 只需要证明只需要证明G中无回路。中无回路。 反证，反证，若若G有回路有回路(v,v1,vk,v)，则，则 从从v到到v1将有两条简单路：将有两条简单路：(v, v1)和和(v,vk, v1)，矛盾。故矛盾。故G中无回路。所以，中无回路。所以，G是树。是树。 1)4)；因为因为G是树，所以是树，所以G中无回路。中无回路。 往证：往证：G有有(n-1)条边。对条边。对n用归纳法。

7、用归纳法。n=1时，命题显然。时，命题显然。假如对于假如对于(n-1)，命题成立。，命题成立。设设G有有n个点，由引理个点，由引理4.2.1知，知，G有点有点vn，且，且vn 恰有一个相邻点恰有一个相邻点vn-1，删去，删去vn和和vnvn-1得一图得一图G。 往证往证G是树：因为是树：因为G无回路，所以无回路，所以G无回路。无回路。 因为因为G连通，所以连通，所以G中任意两点间有路连接。中任意两点间有路连接。 因为因为vn恰有一个相邻点恰有一个相邻点vn-1，故点，故点vn只能出现只能出现在在G中任意一条路的两端，而不能出现在中间。中任意一条路的两端，而不能出现在中间。所以边所以边vnvn-

8、1只能出现在任何一条路的两端，所只能出现在任何一条路的两端，所以删去点以删去点vn和边和边vnvn-1，剩下的图中任意两点间，剩下的图中任意两点间仍有路，故仍有路，故G连通。连通。 因此，因此，G是树。是树。 由归纳假设，由归纳假设，G有有 (n-1)-1=(n-2)条边。故条边。故G有有(n-2)+1=(n-1)条边。条边。 4)5)；已知已知G中无回路，有中无回路，有n个点，个点，(n-1)条边，往证条边，往证G连通。对连通。对n用归纳法。用归纳法。n=2，命题显然。，命题显然。假设假设n-1时时, 命题成立。命题成立。设设G有有n个点。由引理个点。由引理4.2.1知，知，G中有点中有点v

9、n，vn恰有恰有一相邻点一相邻点vn-1，删去点，删去点vn和边和边vnvn-1 得图得图G，显然，显然，G中仍无回路。但中仍无回路。但G有有(n-1)个点，由归纳假设，个点，由归纳假设，G连通。因此，将点连通。因此，将点vn和边和边vnvn-1添入添入G得得G，G仍连仍连通。通。 5)1)；设设G有有n个点，个点，(n-1)条边，并且连通，往证：条边，并且连通，往证：G是树。显然，只需证是树。显然，只需证G无回路即可。无回路即可。若不然，设若不然，设G有一条回路，则删去回路中任一条边，有一条回路，则删去回路中任一条边，所得之图仍连通。对所得之图仍连通。对G中每一条回路，都用此方法删去中每一条

10、回路，都用此方法删去一边，一边，最后得一个无回路但仍然连通的图最后得一个无回路但仍然连通的图G。由树的。由树的定义，定义，G是树是树。而。而G是由是由G删去删去k(k 0)条边所得，故条边所得，故G仍有仍有n个点，所以由个点，所以由1) )4) )知，知，G有有( (n-1) )条边，但是条边，但是G有有(n-1-k)条边，条边，而而n-1 n-1-k( (因为因为k 0) )，矛盾。矛盾。 定理证毕。定理证毕。 推论推论4.2.1 任意有限连通图必有一支撑子图是树。任意有限连通图必有一支撑子图是树。 提示：去掉图中每个回路中的任意一条边即可提示：去掉图中每个回路中的任意一条边即可. 今后，此

11、支撑子图称为母图的今后，此支撑子图称为母图的支撑树支撑树。推论推论4.2.2 若若G是有限图是有限图G的支撑树，的支撑树，vv为为G中一边，中一边，且且vv不在不在G中，则中，则G添上边添上边vv后必有回路后必有回路. 提示：提示：根据根据1) 3) ，G是树，是树，G连通无回路，恰有连通无回路，恰有一条从一条从v到到v的简单路，且由的简单路，且由vv不相邻，该路长度大于不相邻，该路长度大于等于等于2，则添加边，则添加边vv后，有回路。后，有回路。 图图G G例例A AB BC CD DE EF FG GH H4.2 作业作业 1 3 4例：铺设一个连接各个城市的铁路网、或者光例：铺设一个连接

12、各个城市的铁路网、或者光纤通信网络。各个城市之间的费用纤通信网络。各个城市之间的费用“预算预算”已已知。知。bacd762fe81443472356321hg定义定义4.2.2 设设G是加权连通图，带有最小权是加权连通图，带有最小权(和和)的支撑树称为权图的支撑树称为权图G的的最优树最优树。 bacd762fe81443472356321hg设权图设权图G=(P, L)是连通的。是连通的。1) 在在L(G)中选一个具有最小权值的边中选一个具有最小权值的边,记为记为l1,令令T= l1 ；2) 从从L(G)-T中取中取li，使得，使得Tli不产生回路不产生回路，并，并且且w(li)最小。如果存在

13、这样的最小。如果存在这样的li，则令，则令T= T li，重复步骤，重复步骤2)；3) 如果不存在这样的如果不存在这样的li，则算法停止。，则算法停止。 铺设一个连接各个城市的光纤通信网络。（单铺设一个连接各个城市的光纤通信网络。（单位：百万元）：位：百万元）：边的权值非降序边的权值非降序: : fh 1, de 1, ef 2, eh 2, ab 2, df 3, dg 3, bg 3, cg 4, ac 4, bh 4, eg 5, bc 6, cd 6, af 7, gh 7, ah 8bacd762fe81443472356321hg设设G=(P，L)是连通权图。于是是连通权图。于是K

14、ruskal算法得到算法得到的的 T=l1, l2, , ln是是G的的最优树最优树。 分析：认为分析：认为T=l1, l2, , ln是图的一种形式化表是图的一种形式化表示方法，示方法，T中包括中包括n条边，并包括每条边的端点条边，并包括每条边的端点. 待证的是待证的是“T是是G的最优树的最优树”。分成两部分：。分成两部分：先证明先证明T是树，而且是是树，而且是G的支撑子树；再证明的支撑子树；再证明T是权和最小的支撑子树（最优树）。是权和最小的支撑子树（最优树）。 书上的证明过程分为书上的证明过程分为4步，前步，前3步证明步证明T是是G的支撑子树，第的支撑子树，第4步证明步证明T是最优树。是

15、最优树。设设G=(P，L)是连通权图。于是是连通权图。于是Kruskal算法得到的算法得到的 T= l1, l2, , ln是是G的的最优树最优树。 证明：证明：显然显然T=l1, l2, , ln是是G的子图。记的子图。记T=(P1, L1)。1) 先证明先证明T是是支撑子图支撑子图，即证明，即证明P1(T)=P(G)。容易看出容易看出P1(T) P(G)，只需证，只需证P(G) P1(T)。 用反证法，设用反证法，设x P(G)，但，但x P1(T)，任取，任取T中点中点y，因因G是连通的，所以在是连通的，所以在G中有中有x到到y的路，设为的路，设为l=(x,v1,vr,y)，则，则xv1

16、不是不是T中的边中的边(否则否则,将推出将推出x P1(T) )，把边，把边xv1加入加入T中不会产生回路，与算法停中不会产生回路，与算法停于于T矛盾。故必有矛盾。故必有P(G) P1(T) ，所以，所以，P(G)=P1(T)。 2）证明）证明T是一个树是一个树，只须证明，只须证明T是连通的是连通的(无回无回路由算法保证路由算法保证)。 若若T不连通，不妨假设不连通，不妨假设T1和和T2 是是T的其中两的其中两个分支个分支 ，令，令x T1，y T2，因，因G是连通的，所以是连通的，所以有有G中的路中的路 (v1, , vr, vr+1)，其中，其中x= v1,y= vr+1,因因此，必有边此

17、，必有边 vi vi+1，使，使 vi T1，vi+1 T1，那么，那么，把把 vivi+1加到加到T中，不会产生回路，与算法停于中，不会产生回路，与算法停于T矛盾，所以矛盾，所以T是连通的。是连通的。 3）由算法及由算法及1）、）、2）知，）知，T是是G的的支撑树支撑树。设。设G有有r个点，于是个点，于是T也有也有r个点。由定理个点。由定理4.2.1知，知，T有（有（r-1）条边。故）条边。故n=r-1。 4）证明证明T是最优支撑树，我们证明是最优支撑树，我们证明,可以通过以可以通过以下不断交换边的办法，使下不断交换边的办法，使T的所有边全在某一最的所有边全在某一最优支撑树优支撑树T中，则中

18、，则T=T(均有均有r-1条边条边)。设设T*是一棵最优支撑树，是一棵最优支撑树，T*=l1，lr-1，T= l1，lr-1， 若若l1 T*，在，在T*中加入中加入l1，则形成一含有，则形成一含有l1的回路，在此回路中删去一条非的回路，在此回路中删去一条非l1的边，的边，不妨设为不妨设为l1，得一图，得一图T， 令令T= l1,l2,lr-1，则，则T是支撑树。是支撑树。 对任意对任意l L(G)，按照算法的选择边的规，按照算法的选择边的规则，有则，有w(l1) w(l) ，所以，所以w(l1) w(l1)，而而w(T)= w (T*) -w (l1)+w (l1)，所以，所以w (T) w(T*)，即，即T也是最优树。也是最优树。 一般地，设一般地，设l1, , lk T*，lk+1 T*，T=l1, , lk，lk+1, , lr-1，T*=l1, , lk, lk+1, , lr-1因为因为T*是支撑树，是支撑树，T* lk+1必然有回路必然有回路C，不妨，不妨设设lk+1是回路中一条边，是回路中一条边，lk+1 T，令令T=