1第二十七讲树讲授内容： 1.无向树 无向树，森林 树的等价定义 基本结论 2.生成树 生成树 基本回路 基本割集 基本回路与基本割集的关系 3.最小生成树及其求解算法 取小法 去大法讲授重点：树基本概念，等价定义，最小生成树讲授难点：基本回路与基本割集的关系第二十七讲树1.无向树无向树：连通而无简单回路连通而无简单回路的无向图称为无向树,简称树树(tree) 树叶树叶(leave)：树中度数为1的顶点 分枝点分枝点(branched node)或或内部结点内部结点：树中度数大于1的顶点空树空树：：单一孤立结点称为空树空树或或平凡树平凡树(null tree) 2.森林森林(forest):一个无简单回路一个无简单回路的无向图， 或 一个无向图的每个连通分支均是树时, 树是森林一、无向树例如图8.6―1(a)、(b)所示的都是树,(c)所示的是森林图 8.6―1 定理1：无向图T是树,当且仅当下列5条之一成立 (或者说,这5条的任一条都可作为树的定义) (1)无简单回路且m=n-1的图m：边数,n：顶点数 (2) 连通且m=n-1的图 (3)无简单回路,但增加任一新边,得到且仅得到一条基 本回路。
(4)连通但删去任一边,图便不连通(n≥2) (5)每一对顶点间有唯一的一条基本路径 (n≥2)一、无向树证明思路：证明思路：6 6个命题可以循环推出个命题可以循环推出1.无向树无向树：连通而无简单回路连通而无简单回路的无向图称为无向树,简称树树证明：轮转法树的定义(1)(5) (2)(4) (3)一、无向树对n归纳法反证法N归纳法证明：1) 树的定义连通而无简单回路连通而无简单回路(1)无简单回路且无简单回路且 m=n-1的图的图 对n作归纳 n=1时,m=0,显然m=n-1 假设n=k时命题成立, 即m=n-1 现考察n=k+1时的情况T： 由于树T是连通而无简单回路,所以T 中存在v ∈V , 使得d(v)=1,在T中删去v及其关联边,便得到k个顶点 的连通无简单回路图T‵由于树T是连通而无简单回路,所以T 中存在v ∈V , 使得d(v)=1,在T中删去v及其关联边,便得到k个顶点 的连通无简单回路图T‵ T‵有k个顶点，由归纳假设T‵T‵有k-1条边 (再将顶点v及其关联边加回得到原图T) 所以,T中含有k+1个顶点和k条边,符合公式m=n-1。
所以,树是无简单回路且m=n-1的图树是无简单回路且m=n-1的图一、无向树2一个重要结论：一个重要结论： 无向图G=为连通图，若G无简单回 路，则必存在v0 ∈V ,使得d(v0)=1无向图G=为连通图，若G无简单回 路，则必存在v0 ∈V ,使得d(v0)=1 或为： 无向图G=为连通图，则或者存在v0 ∈V ,使得d(v0)=1 ，或者G存在简单回路无向图G=为连通图，则或者存在v0 ∈V ,使得d(v0)=1 ，或者G存在简单回路一、无向树 2) (1)无简单回路且无简单回路且m=n-1的图的图(2)连通且连通且m=n-1的图的图 用反证法若图不连通,设T有k个连通分图 (k≥2)T1,T2,…,Tk, 其顶点数分别:n1,n2,…,nk, 边数分别:m1,m2,…,mk,11,kkii iinnmm====∑∑于是11(1)1kkii iimmnnkn====−=−1)此时因T连通且m=n-1=k, T至少有一顶点v使得d(v)=1 (因为假如T 的每个顶点(n个)的次数都≥2,即d(v) ≥2,则于是有m≥k+1,这与m=k矛盾)3) (2)连通且连通且m=n-1的图的图(3)无简单回路无简单回路,但增加任一新边但增加任一新边,得到且 仅得到一条基本回路得到且 仅得到一条基本回路。
(a) 证T无简单回路，对n作归纳证明 n=1时,m=n-1=0,显然无简单回路 假设顶点数n=k时无简单回路, 现考察顶点数是n=k+1时的情况T ：一、无向树) 1(22)(21111+=≥=∑∑+=+=kvdmkikii我们删去T 中v及其关联边得到新图T′,根据归纳假设T′无简 单回路,再加回v及其关联边又得到图T,则T也无简单回路3) (2)连通且连通且m=n-1的图的图(3) (b) 下证增加任一边下证增加任一边(vi,vj),得到且仅得到一条基本回路得到且仅得到一条基本回路 由于T连通，从vi到vj有一条基本路径，再加上边 (vi,vj)得到一条基本回路. 假设增加一边一边(vi,vj)得到两条基本回路，则删除 边(vi,vj)后必有一简单回路，这与T无简单回路相 矛盾一、无向树4) (3)无简单回路无简单回路,但增加任一新边但增加任一新边,得到且仅得到一条基 本回路得到且仅得到一条基 本回路(4)连通但删去任一边连通但删去任一边,图便不连通图便不连通(n≥≥2) 若图不连通,则存在两个顶点vi和vj,在vi和vj之 间没有路径,若加边(vi,vj)不会产生基本回路,但这 与假设矛盾。
由于由于T无简单回路无简单回路,所以删去任一边所以删去任一边,图便不连通图便不连通一、无向树5) (4)连通但删去任一边连通但删去任一边,图便不连通图便不连通(n≥≥2)(5)每一对顶点 间有唯一的一条基本路径每一对顶点 间有唯一的一条基本路径(n≥≥2) 由连通性知由连通性知,任两点间有一条路径任两点间有一条路径,于是有一条基本 路径于是有一条基本 路径若此基本路径不唯一,则T中含有简单回路,删去 此回路上任一边,图仍连通,这与假设不符,所以通路是 唯一的6) (5)每一对顶点间有唯一的一条基本路径每一对顶点间有唯一的一条基本路径(n≥≥2)树的定 义 (连通而无简单回路连通而无简单回路) 显然连通若有简单回路,则回路上任两点间有 两条基本路径,此与基本路径的唯一性矛盾一、无向树?最小的连通图最小的连通图：删去任一条边，图就不再连通；?最大的无回路图最大的无回路图：加上任一条边(不是环也不是平行 边)，图中会产生回路最小的连通图最小的连通图：删去任一条边，图就不再连通；?最大的无回路图最大的无回路图：加上任一条边(不是环也不是平行 边)，图中会产生回路1 12 23 34 4 5 56 67 78 8 9 93一、无向树定理2 任一树T中,至少有两片树叶(n≥2时)。
证明：反证法反证法， 若若T中每个顶点的次数≥中每个顶点的次数≥2,则 2m=Σdeg(vi)≥2n,得m ≥n,这与m=n-1矛盾 若若T中只有一个顶点次数为中只有一个顶点次数为1,其它顶点次数≥其它顶点次数≥2 则 2m=Σdeg(vi)≥2(n-1)+1=2n-1,得2m ≥2n-1, 这与2m=2n-2矛盾 所以,T中至少有两个顶点次数为1二、生成树3.生成树：给定一个无向图G,若G的一个生成子 图T是树,则称T为G的生成树或支撑树生成树：给定一个无向图G,若G的一个生成子 图T是树,则称T为G的生成树或支撑树图 8.6―2 图图G的生成树不是唯一的的生成树不是唯一的,如图8.6―2所示,右侧两个图都 是左侧图G的生成树二、生成树定理定理3:任何连通无向图至少有一棵生成树任何连通无向图至少有一棵生成树 证明：构造法，G连通无向图 若若G没有简单回路没有简单回路,则G本身就是生成树 若若G仅有一个简单回路仅有一个简单回路,从此简单回路中删去 一条边,仍保持图的连通性,即得一棵生成树 若若G有多个简单回路有多个简单回路,则逐个地对每个回路重 复上述过程,直至得到一棵生成树为止二、生成树4. 设T为图G的一棵生成树，称T中的边称为T的树枝,不在生成树T中但属于图G的边,称为树T的弦。
弦的集合称为树T的补图 8.6―2 在图8.6―2(a)中,若生成树取为(b)图,则e2,e6,e8,e3是树 枝,e1,e5,e7,e4都是弦,{e1,e5,e7,e4}是该生成树的补5. 设G=是无向图, 若存在边子集E`⊂E ，使得图G删除E`后所得子图 G-E`的连通分支数W(G- E`)>W(G)； 而删除E`的任一真子集E“后所得子图G-E”的连通分 支数W(G- E“)=W(G), 则称E`为为G的一个边割集的一个边割集 若若G的一个边割集中只含有一条边，则称该边为割边的一个边割集中只含有一条边，则称该边为割边 例如,在图8.5―10中{e2,e3,e4}是一割集,{e4,e5}也是 割集但{e4,e5,e6}不是割集,虽然删去它G变成不连 通,但不符合条件2二、生成树二、生成树5. 设G=是无向图, 若存在边子集E`⊂E ，使得图G删除E`后所得子图 G-E`的连通分支数W(G- E`)>W(G)； 而删除E`的任一真子集E“后所得子图G-E”的连通分支数W(G- E“)=W(G), 则称E`为为G的一个边割集的一个边割集若若G的一个边割集中只含有一条边，则称该边为割边。
的一个边割集中只含有一条边，则称该边为割边图 8.5―10例如,在图8.5―10中{e2,e3,e4}是一割集,{e4,e5}也是割集但 {e4,e5,e6}不是割集,虽然删去它G变成不连通,但不符合条件246.设连通图G有n个顶点,m条边,则G的任一生成树有的任一生成树有 n-1条树枝条树枝,m-n+1条弦条弦在图G中,给定生成树T后, 根据定理1的第(3)条,每加一条弦,则得一个基本回 路, 例如在图8.6―2中,若树的边集是{e2,e3,e6,e8}, 则加弦e1,得基本回路{e1,e2,e6,e8} 加弦e5,得基本回路{e5,e2,e6} 加弦e7,得基本回路{e7,e6,e3} 加弦e4,得基本回路{e4,e8,e6,e3} 因为有因为有m-n+1条弦条弦,一般地可得一般地可得m-n+1个基本回 路个基本回 路,此此m-n+1个基本回路称为图G的关于生成树T的 基本回路系统个基本回路称为图G的关于生成树T的 基本回路系统二、生成树图 8.6―2 6.设连通图G有n个顶点,m条边,则G的任一生成树有的任一生成树有n-1条树枝条树枝,m-n+1条弦条弦 在图G中,给定生成树T后,根据定理1的第(3)条,每加一条弦,则得一个基 本回路, 例如在图8.6―2中,若树的边集是{e2,e3,e6,e8},则加弦e1,得基本回路 {e1,e2,e6,e8}。
加弦e5,得基本回路{e5,e2,e6} 加弦e7,得基本回路{e7,e6,e3} 加弦e4,得基本回路{e4,e8,e6,e3} 因为有因为有m-n+1条弦条弦,一般地可得一般地可得m-n+1个基本回路个基本回路,此此m-n+1个基本回 路称为图G的关于生成树T的基本回路系统个基本回 路称为图G的关于生成树T的基本回路系统二、生成树7. 从树从树T中删去一条枝中删去一条枝,将将T分为两棵树分为两棵树,G的顶点集划 分为两个子集的顶点集划 分为两个子集,连结这两个子集的边集就是对应于 这条枝的割集连结这两个子集的边集就是对应于 这条枝的割集,称为称为对应于这条边的基本割集对应于这条边的基本割集 例如在图8.6―2中,若树枝集是{e2,e3,e6,e8},则 对应于树枝e2的基本割集是{e2,e1,e5}, 对应于树枝e6的基本割集是{e1,e5,e6,e7,e4}, 对应于树枝e8的基本割集是{e1,e8,e4}, 对应于树枝e3的基本割集是{e3,e7,e4}定理定理4：一条简单回路和任何生成树的补至 少有一条共同边：一条简单回路和任何生成树的补至 少有一条共同边 证明：反证法反证法：假如有一条简单回路和一 棵生成树的补没有共同边假如有一条简单回路和一 棵生成树的补没有共同边,那么这简单回路 包含在生成树中。
然而这是不可能的因 为一棵树不包含简单回路,证毕二、生成树定理5：一个割集和任何生成树至少有一条共同边定理5：一个割集和任何生成树至少有一条共同边。