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

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,

12、l2, , ln是是G的最优树。的最优树。 证明：证明：显然显然T= l1, l2, , ln是是G的子图。记的子图。记T=(P1, L1)。1) 先证明先证明T是支撑子图，即证明是支撑子图，即证明P(T)=P(G)。容易看出容易看出P(T) P(G)，只需证只需证P(G) P(T)。用反证法，设用反证法，设x P(G)，但但x P(T)，任取任取T中点中点y，因因G是连通的，所以在是连通的，所以在G中有中有x到到y的路设为的路设为l=(x,v1,vr,y)，则则x v1不是不是T中的边，把边中的边，把边x v1加加入入T中不会产生回路，与算法停于中不会产生回路，与算法停于T矛盾。故必矛盾。故

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

14、盾，所以T是连通的。是连通的。 3）由算法及由算法及1）、）、2）知，）知，T是是G的支撑树。设的支撑树。设G有有r个点，于是个点，于是T也有也有r个点。由定理个点。由定理4.2.1知，知，T有（有（r-1）条边。故条边。故n=r-1。 4）证明证明T是最优支撑树，我们证明是最优支撑树，我们证明,可以通过以可以通过以下不断交换边的办法，使下不断交换边的办法，使T的所有边全在某一最的所有边全在某一最优支撑树优支撑树T中，则中，则T=T(均有均有r-1条边条边)。设设T*是一棵最优支撑树，是一棵最优支撑树，T*=l1，lr-1，T= l1，lr-1， 若若l1 T*，在在T*中加入中加入l1，则形

15、成一含有则形成一含有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必

16、然有回路必然有回路C，不妨不妨设设lk+1是回路中一条边，是回路中一条边，lk+1 T，令令T= l1,lk,lk+1,lk+2,lr-1，则则T是支撑树，是支撑树，由由Kruskal算法步骤算法步骤2)，在算法实行中选了在算法实行中选了lk+1而而没选没选lk+1，说明说明w(lk+1) w (lk+1) 所以所以w(T)=w(T*)-w(lk+1)+w(lk+1)，即即w(T) w(T*) 因为因为T*是最优树，所以是最优树，所以T也是最优树，但也是最优树，但T包包括括l1，lk+1，反复执行上述过程，最后可得一反复执行上述过程，最后可得一最优树包括了最优树包括了T的所有边，即的所有边，即

17、T=T，所以所以T是最是最优树。优树。 铺设一个连接各个城市的光纤通信网络。铺设一个连接各个城市的光纤通信网络。（单位：万元）（单位：万元）febacd546036388404820452815383062251210hg 由定理由定理4.2.1、定理、定理4.2.2及其证明知道：及其证明知道：1)支撑树加上一条非树中的边后包含一个唯一支撑树加上一条非树中的边后包含一个唯一的回路；的回路；2)支撑树删去一条树中的边后形成两个子树，支撑树删去一条树中的边后形成两个子树，图中两个端点分属于两个子树的边称为割。图中两个端点分属于两个子树的边称为割。定理定理4.2.3 支撑树支撑树T*是最优树的充要条

18、件是：是最优树的充要条件是：对对T*中的任意一条边，将该边从中的任意一条边，将该边从T*中删除后形中删除后形成的割中，该边的权最小。成的割中，该边的权最小。定理定理4.2.4 支撑树支撑树T*是最优树的充要条件是：是最优树的充要条件是：对属于对属于G但不属于但不属于T*的任意一条边，将该边加入的任意一条边，将该边加入到到T*中后形成的回路中，该边的权最大。中后形成的回路中，该边的权最大。通常称定理通常称定理4.2.3为割最优条件，定理为割最优条件，定理4.2.4为圈为圈（回路）最优条件。（回路）最优条件。 首先证明定理首先证明定理4.2.3。必要性，假设被删掉的边在形成的。必要性，假设被删掉的

19、边在形成的割集中权不是最小的，这与求最优树割集中权不是最小的，这与求最优树T*的的Kruskal算法矛算法矛盾，因此假设不成立，该边在形成的割集中权是最小的。盾，因此假设不成立，该边在形成的割集中权是最小的。充分性，由求充分性，由求T*的的Kruskal算法及定理算法及定理4.2.2的证明过程知的证明过程知T*是最优树。是最优树。现在来证明定理现在来证明定理4.2.4。必要性，假设该边的权在此回路。必要性，假设该边的权在此回路中不是最大的，边中不是最大的，边l的权最大，那么在求的权最大，那么在求T*的的Kruskal算法算法进行过程应该选择该边加入集合进行过程应该选择该边加入集合l1, l2, ,li中，而不是中，而不是l，这与这与l是是T*中的边矛盾，即假设不成立，该边的权在此回中的边矛盾，即假设不成立，该边的权在此回路中权最大。路中权最大。充分性，由求充分性，由求T*的的Kruskal算法及定理算法及定理4.2.2的证明过程知的证明过程知T*是最优树。是最优树。 1)任取任取v0 P(G)，取取l1 L(G)，满足满足l1以以v0为端点，为端点，且且w(l1)最小。记最小。记l1的另一个端点为的另一个端点为v1，令令T= l1，S=v0, v12)如果如果T= l1