《离散数学》课件：4-2-树

《《离散数学》课件：4-2-树》由会员分享，可在线阅读，更多相关《《离散数学》课件：4-2-树（30页珍藏版）》请在文档大全上搜索。

1、1847年德国物理学家柯希霍夫(kirchhof)提出了树的概念.即所谓无圈连通图,他时在研究电路网络时考虑电路网的所谓”生成树”,即一个含有电路图上所有节点的树形子图.1857年英国数学家凯莱(caylay Arthur)研究碳氢化合物时,提出了树的概念与记数的理论.1889年凯莱给出了完全图Kn的概念.例如10个顶点的完全图竟有一亿棵生成树.1956年Kruskal设计了求最优树的有效算法.定义定义4.2.1 设设G=( (P，L)是图。如果是图。如果G是连通的，是连通的，并且无回路，则称并且无回路，则称G为树。无回路的图为树。无回路的图( (可能可能不连通不连通) )也称为森林。也称为森

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

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

4、 )3) )；因为因为G连通，所以对于连通，所以对于v, ,v, ,有有从从v到到v的路，取其最短者，得从的路，取其最短者，得从v到到v的的简单路。若有两条这样的路，设为简单路。若有两条这样的路，设为 (v, ,v1, , ,vn, ,vn+1) ，(v, ,v1, , ,vm, ,vm+1)，其中其中vn+1=vm+1=v。从左向右看可找到最从左向右看可找到最小的小的k，使得使得vk vk。于是，从于是，从G删去边删去边vk-1vk，从从vk-1到到vk还有路还有路 (vk-1, ,vk, , ,vm+1, ,vn, ,vn-1, , ,vk)。故故G删去删去边边vk-1vk后，所得之图仍连

5、通，矛盾。后，所得之图仍连通，矛盾。 3) )1) )；由已知条件知，由已知条件知，G是连通的。若是连通的。若G有回路有回路( (v,v1, , ,vk, , ,v) )，则从则从v到到v1将有两条简单路：将有两条简单路：( (v, v1) )和和( (v, , ,vk, , , v1) )，矛盾。故矛盾。故G中无回路，所以，中无回路，所以，G是树。是树。 1) )4) )；因为因为G是树，所以是树，所以G中无回路。往证：中无回路。往证：G有有(n-1)条边。对条边。对n用归纳法。用归纳法。n=1时，命题显然。时，命题显然。假如对于假如对于(n-1)，命题成立。命题成立。设设G有有n个点，由引

6、理个点，由引理1知，知，G有点有点vn，且且vn 恰恰有一个相邻点有一个相邻点vn-1，删去删去vn和和vnvn-1得一图得一图G。因为因为G无回路，所以无回路，所以G无回路。无回路。因为因为G连通，所以连通，所以G中任意两点间有路连接。中任意两点间有路连接。因为因为vn恰有一相邻点恰有一相邻点vn-1，故点故点vn只能出现在只能出现在G中中任意一条路的两端，而不能出现在中间。所以边任意一条路的两端，而不能出现在中间。所以边vnvn-1只能出现在任何一条路的两端，所以删去只能出现在任何一条路的两端，所以删去点点vn和边和边vnvn-1，剩下的图中任意两点间仍有路，剩下的图中任意两点间仍有路，故

7、故G连通。连通。因此，因此，G是树。由归纳假设，是树。由归纳假设，G有有 (n-1)-1=(n-2)条边。故条边。故G有有(n-2)+1=(n-1)条边。条边。 采用归纳法。当采用归纳法。当G只有一个节点、两个节点时显然只有一个节点、两个节点时显然命题成立。假设节点数命题成立。假设节点数 k时成立，则节点数为时成立，则节点数为k+1时设时设G1， G2 ， Gt是是G的的t个连通分支个连通分支(t 1)。若若t1，则由则由G1， G2 ， Gt是树，知是树，知 L(G) = L(G1) + L(G2) + L(Gt) = P(G1) -1+ P(G2) -1+ L(Gt) -1= P(G) -

8、t，矛盾矛盾4)5)；已知已知G中无回路，有中无回路，有n个点，个点，(n-1)条边，条边，往证往证G连通。对连通。对n用归纳法。用归纳法。n=2，命题显然。命题显然。假设假设n-1时时, 命题成立。命题成立。设设G有有n个点。由引理个点。由引理1知，知，G中有点中有点vn，vn恰有恰有一相邻点一相邻点vn-1，。，。删去点删去点vn和边和边vnvn-1 得图得图G，显显然，然，G中仍无回路。但中仍无回路。但G有有(n-1)个点，由归纳个点，由归纳假设，假设，G连通。因此，将点连通。因此，将点vn和边和边vnvn-1添入添入G得得G，G仍连通。仍连通。 5)1)；设设G有有n个点，个点，(n-

9、1)条边，并且连通，条边，并且连通，往证：往证：G是树。显然，只需证是树。显然，只需证G无回路即可。无回路即可。若不然，设若不然，设G有一条回路，则删去回路中任一有一条回路，则删去回路中任一条边，所得之图仍连通。对条边，所得之图仍连通。对G中每一条回路，都中每一条回路，都用此方法删去一边，最后得一个无回路但仍然连用此方法删去一边，最后得一个无回路但仍然连通的图通的图G。所以所以G是树。而是树。而G是由是由G删去删去k(k 0)条边所得，故条边所得，故G仍有仍有n个点，所以由个点，所以由1) )4) )知，知，G有有( (n-1) )条边，但是条边，但是G有有(n-1-k)条边，而条边，而n-1

10、 n-1-k( (因为因为k 0) )，矛盾。矛盾。定理证毕。定理证毕。 推论推论1 任意有限连通图必有一支撑子图是树。任意有限连通图必有一支撑子图是树。今后，此支撑子图称为母图的支撑树。今后，此支撑子图称为母图的支撑树。推论推论2 若若G是有限图是有限图G的支撑树，的支撑树，vv为为G中一边，中一边，且且vv不在不在G中，则中，则G添上边添上边vv后必有回路。后必有回路。 例：铺设一个连接各个城市的光纤通信网络。例：铺设一个连接各个城市的光纤通信网络。bacd762fe81443472356321hg定义定义4.2.2 设设G是加权连通图，带有最小权是加权连通图，带有最小权(和和)的支撑树称

11、为权图的支撑树称为权图G的最优树。的最优树。 bacd762fe81443472356321hg设权图设权图G=(P, L)是连通的。是连通的。1) 在在L(G)中选一个具有最小权值的边，记为中选一个具有最小权值的边，记为l1，令令T= l1 ；2) 从从L(G)-T中取中取li，使得使得Tli不产生回路，并不产生回路，并且且w(li)最小。如果存在这样的最小。如果存在这样的li，则令则令T= T li，重复步骤重复步骤2)；3) 如果不存在这样的如果不存在这样的li，则算法停止。则算法停止。 设设G=(P，L)是连通权图。于是是连通权图。于是Kruskal算法得到算法得到的的 T= l1,