离散数学(7.7树与生成树)ppt课件.ppt
7.5 树与生成树(Trees and Spanning Trees)7.5.1 无向树无向树(Undirected Trees)7.5.2无无向向图图中中的的生生成成树树与与最最小小生生成成树树(Spanning Trees and Minimal Spanning Trees)7.5.1 无向树(Undirected Trees)树树是是图图论论中中的的一一个个重重要要概概念念。早早在在1847年年克克希希霍霍夫夫就就用用树树的的理理论论来来研研究究电电网网络络，1857年年凯凯莱莱在在计计算算有有机机化化学学中中2H2n+2的的同同分分异异构构物物数数目目时时也也用用到到了了树树的的理理论论。而而树树在在计计算算机机科科学学中中应应用用更更为为广广泛泛。本本节节介介绍绍树树的的基基本本知识，知识，其中谈到的图都假定是简单图。其中谈到的图都假定是简单图。定定义义7.5.1 一一个个连连通通无无圈圈无无向向图图称称为为无无向向树树(简简称称为为树树)。记记作作T。树树中中度度数数为为1的的结结点点称称为为树树叶叶（或或终终端端结结点点），度度数数大大于于的的结结点点称称为为分分枝枝点点（或或内内点点，或或非非终终端端结结点点）。一一个个无无圈圈图图称为森林。称为森林。显显然然若若图图G是是森森林林，则则G的的每每个个连连通通分分支支是是树树。如如图图7.5.1(a)所所示示的的是一棵树；是一棵树；(b)所示的是森林。所示的是森林。图图 7.5.1 树和森林示意图树和森林示意图 【例例7.5.1】判判断断图图 7.5.2中中各各图图是是否否为树为树.图图 7.5.2 证证：因因为为 T是是一一棵棵n的的（n，m）树树，所以由定理所以由定理7.5.1，有有若若T中的无树叶，中的无树叶，则则T中每个顶点的度数中每个顶点的度数2,则则 deg(vi)2n,（2）若若T中中只只有有一一片片树树叶叶，则则T中中只只有有一一个个结结点点度度数数为为1,其其它它结结点度数点度数2,所以所以 (1)(3)(2),(3)都与都与(1)矛盾。所以矛盾。所以T中至少有两片树叶。证毕。中至少有两片树叶。证毕。定理定理7.5.1 任一树任一树T中中,至少有两片树叶至少有两片树叶(n2时时)。定理定理7.5.2一个无向图（一个无向图（n,m）图）图T是树是树,当且仅当下列当且仅当下列5条之一成立。条之一成立。(或者说或者说,这这5条的任一条都可作为树的定义。条的任一条都可作为树的定义。)(1)无圈且无圈且m=n-1。(2)连通且连通且m=n-1。(3)无无圈圈,但但增增加加任任一一新新边边,得得到到且且仅仅得得到一个圈。到一个圈。(4)连连通通但但删删去去任任一一边边,图图便便不不连连通通(n2)。(5)每每一一对对结结点点间间有有唯唯一一的的一一条条通通路路。(n2)。证证:(1)证证明明由由树树的的定定义义可可知知T无无圈。下证圈。下证m=n-1。对对n作归纳。作归纳。n=1时时,m=0,显然显然m=n-1。假假 设设 n=k时时 命命 题题 成成 立立,现现 证证 明明n=k+1时也成立。时也成立。由于树是连通而无圈由于树是连通而无圈,所以至少有所以至少有一个度数为一个度数为1的结点的结点v,在在T中删去中删去v及其关及其关联边联边,便得到便得到k个结点的连通无圈图。由个结点的连通无圈图。由归纳假设它有归纳假设它有k-1条边。再将顶点条边。再将顶点v及其及其关联边加回得到原图关联边加回得到原图T,所以所以T中含有中含有k+1个顶点和个顶点和k条边条边,符合公式符合公式m=n-1。所以树是无圈且所以树是无圈且m=n-1的图。的图。(2)证明由第证明由第(1)条可推出第条可推出第(2)条。条。用反证法。若图不连通用反证法。若图不连通,设设T有有k个连个连通分支通分支(k2)T1,T2,Tk,其结点其结点数分数分别别是是n1,n2,nk,边边数分数分别为别为m1,m2,mk,于是于是得出矛盾。所以得出矛盾。所以T是连通且是连通且m=n-1的图。的图。(3)证明由第证明由第(2)条可推出第条可推出第(3)条。条。首先证明首先证明T无圈。对无圈。对n作归纳证明。作归纳证明。n=1时时,m=n-1=0,显然无圈。显然无圈。假设结点数为假设结点数为n-1时无圈时无圈,今考察结今考察结点数是点数是n的情况。此时至少有一个结点的情况。此时至少有一个结点v其度其度数数deg(v)=1。我们删去。我们删去v及其关联边得到新及其关联边得到新图图T,根据归纳假设根据归纳假设T无圈无圈,再加回再加回v及其关联及其关联边又得到图边又得到图T,则则T也无圈。也无圈。其次其次,若在连通图若在连通图T中增加一条新边中增加一条新边(vi,vj),则由于则由于T中由中由vi到到vj存在一条通路存在一条通路,故必有故必有一个圈通过一个圈通过vi,vj。若这样的圈有两个，则。若这样的圈有两个，则去掉去掉(vi,vj),T中必存在通过中必存在通过vi,vj的圈，与的圈，与T无圈矛盾。故加上边无圈矛盾。故加上边(vi,vj)得到一个切仅得到一个切仅一个圈。一个圈。(4)证明由第证明由第(3)条可推出第条可推出第(4)条。条。若图不连通若图不连通,则存在两个结点则存在两个结点vi和和vj,在在vi和和vj之间没有路之间没有路,若加边若加边(vi,vj)不会产不会产生简单回路（圈）生简单回路（圈）,但这与假设矛盾。由于但这与假设矛盾。由于T无圈无圈,所以删去任一边所以删去任一边,图便不连通。图便不连通。(5)证明由第证明由第(4)条可推出第条可推出第(5)条。条。由连通性知由连通性知,任两点间有一条路径任两点间有一条路径,于是有一条通路。若此通路不唯一于是有一条通路。若此通路不唯一,则则T中中含有简单回路含有简单回路,删去此回路上任一边删去此回路上任一边,图仍图仍连通连通,这与假设不符这与假设不符,所以通路是唯一的。所以通路是唯一的。(6)证证明明由由第第(5)条条可可推推出出树树的的定定义。义。显然连通。若有圈显然连通。若有圈,则圈上任意两则圈上任意两点间有两条通路点间有两条通路,此与通路的唯一性矛盾。此与通路的唯一性矛盾。证毕。证毕。由由定定理理7.5.2所所刻刻画画的的树树的的特特征征可可见见：在在结结点点数数给给定定的的所所有有图图中中，树树是是边边数数最最少少的的连连通通图图，也也是是边边数数最最多多的的无无圈圈图图。由由此此可可知知，在在一一个个（n，m）图图G中中，若若mn1，则则G是是不不连连通通的的；若若mn1，则则G必定有圈。必定有圈。【例例7.5.2】T是是一一棵棵树树,有有两两个个2度度结结点点，一一个个3度结点，三个度结点，三个 4度结点，度结点，T有几片树叶？有几片树叶？解：解：设树设树T有有x片树叶，则片树叶，则T的结点数的结点数 n=2+1+3+x T的边数的边数 m=n-1=5+x 又由又由 得得 2 （5+x）=22+31+43+x 所以所以x=9，即树，即树T有有9片树叶。片树叶。7.5.2无无向向图图中中的的生生成成树树与与最最小小生生成成树树(Spanning Trees and Minimal Spanning Trees)定定义义7.5.2 若若无无向向(连连通通图图)G的的生生成成子子图图是是一一棵棵树树，则则称称该该树树是是G的的生生成成树树，记记为为TG。生生成成树树TG中中的的边边称称为为树树枝枝。图图G中中其其它它边边称称为为TG的的弦弦。所所有有这这些些弦弦的的集集合合称为称为TG的补。的补。如如图图7.5.3中中(b)、(c)所所示示的的树树T1、T2是是(a)图图的的生生成成树树，而而(d)所所示示的的树树T3不不是是(a)图图的的生生成成树树。一一般般的的，图图的的生生成成树树不唯一。不唯一。图图 7.5.3 考考虑虑生生成成树树T1，可可知知e1，e2，e3，e4是是T1的的树树枝枝，e5，e6，e7是是T1的的弦弦，集集合合e5，e6，e7是是T1的的补补。生生成成树树有有其其一定的实际意义。一定的实际意义。【例例7.5.3】某某地地要要兴兴建建个个工工厂厂，拟拟修修筑筑道道路路连连接接这这处处。经经勘勘测测其其道道路路可可依依如如图图7.5.3(a)图图的的无无向向边边铺铺设设。为为使使这这处处都都有道路相通，有道路相通，问至少要铺几条路？问至少要铺几条路？解解 这这实实际际上上是是求求G的的生生成成树树的的边边数数问问题。题。一一般般情情况况下下，设设连连通通图图G有有n个个结结点点，m条条边边。由由树树的的性性质质知知，T有有n个个结结点点，n1条树枝，条树枝，mn1条弦。条弦。在在图图7.5.3(a)中中，n5，则则n1514，所以至少要修条路才行。所以至少要修条路才行。定定义义7.5.3 设设GV,E是是一一连连通通的的有有权权图图，则则G的的生生成成树树TG为为带带权权生生成成树树,TG的的树树枝枝所所带带权权之之和和称称为为生生成成树树TG的的权权,记记为为C(TG)。G中中具具有有最最小小权权的的生成树生成树TG称为称为G的最小生成树。的最小生成树。求求最最小小生生成成树树问问题题是是有有实实际际意意义义的。的。如如要要建建造造一一个个连连接接若若干干城城市市的的铁铁路路网网络络，已已知知城城市市vi和和vj之之间间直直达达铁铁路路的的造造价价，设设计计一一个个总总造造价价为为最最小小的的铁铁路路网络，网络，就是求最小生成树就是求最小生成树TG。下下 面面 介介 绍绍 求求 TG的的 克克 鲁鲁 斯斯 克克 尔尔（Kruskal)算法。算法。此此方方法法又又称称为为“避避圈圈法法”。其其要要点点是是，在在与与已已选选取取的的边边不不成成圈圈的的边边中选取最小者。中选取最小者。具体步骤如下：具体步骤如下：1)在在G中中选选取取最最小小权权边边，置置边边数数i1。2)当当in1时时，结结束束。否否则则，转转3)。3)设设已已选选择择边边为为 e1,e2,ei，在在G中中选选取取不不同同于于e1,e2,ei 的的边边 ei+1,使使 e1,e2,ei,ei+1无无圈圈且且ei+1是满足此条件的是满足此条件的最小权边最小权边。4)置置i为为i1，转转2)。【例例7.5.4】求求图图7.5.4(0)中中有有权权图图的的最小生成树。最小生成树。解解:因因为为 图图中中n8，所所以以按按算算法法要要执执行行n17次次，其其过过程程见见图图7.5.4中中(1)(7)。图 7.5.4 【例例7.5.5】求求图图7.5.5中中有有权权图图G的的最最小生成树。小生成树。解解:因因为为 图图中中n8，所所以以按按算算法法要执行要执行n17次。次。图 7.5.5 【例例7.5.6】图图7.5.6所所示示的的赋赋权权图图G表表示示七七个个城城市市a,b,c,d,e,f,g及及架架起起城城市市间间直直接接通通讯讯线线路路的的预预测测造造价价。试试给给出出一一个个设设计计方方案案使使得得各各城城市市间间能能够够通通讯讯且且总总造造价价最最小小,并计算出最小造价并计算出最小造价。图图7.5.6 解解:该该问问题题相相当当于于求求图图的的最最小小生生成成树树问问题题，此此图图的的最最小小生生成成树树为为图图7.5.6中中的的TG,因因此此如如图图TG架架线线使使各各城城市市间间能能够够通讯，且总造价最小，最小造价为：通讯，且总造价最小，最小造价为：()2348 小小结结：本本节节介介绍绍了了树树、生生成成树树和和最最小小生生成成树树的的概概念念、树树的的六六种种等等价价定定义义及及最小生成树的求法。最小生成树的求法。重重点点:掌掌握握六六种种等等价价定定义义及及最最小小生生成树的求法。成树的求法。作业作业:P327 (2),(3),(6)
