最小树问题.ppt

第二节最小树问题一、树及其性质定义1:无圈的连通图称为树。树一般用T表示。定理1:任给树T=(V,E),若n(T)≥2,则T中至少有两个悬挂点。证明:设Q=(v1,v2,…,vk)是G中含边数最多的一条初等链,因n(T)≥2,并且T是连通的,故链Q中至少有一条边,从而v1与vk是不同的。现证v1是悬挂点,即d(v1)=1。反证法:如d(v1)≥2,则存在边[v1,vm],使m≠2,若vm不在Q上,v1v2vkvm那么(vm,v1,v2,…,vk)比Q链边数多一条,与Q是边数最多的链矛盾。若vm在Q上v1v2vkvm(v1,v2,…,vm,v1)是圈,与T是树矛盾。所以必有d(v1)=1,即v1是悬挂点。同理可证:vk也是悬挂点。所以G至少有两个悬挂点。(1)T是一个树。(2)T无圈,且m=n-1。(3)T连通,且m=n-1。定理2图T=(V,E),p=n,q=m,则下列关于树的说法是等价的。边数=点数-1(4)T无圈,但每加一条新边即得唯一一个圈。(5)T连通,但每丢掉一条边就不连通。(6)T中任意两点,有唯一链相连。先证明(6)→(1)证明:(1)→(2)由于T是树,由定义知T连通且无圈。只须证明m=n-1。归纳法:当n=2时,由于T是树,所以两点间显然有且仅有一条边,满足m=n-1。假设n=k-1时命题成立,即有k-1个顶点时,T有k-2条边。当n=k时,因为T连通无圈,k个顶点中至少有一个点次为1。设此点为u,即u为悬挂点,设连接点u的悬挂边为[v,u],从T中去掉[v,u]边及点u,不会影响T的连通性,得图T’,T’为有k-1个顶点的树,所以T’有k-2条边,再把(v,u)、点u加上去,可知当T有k个顶点时有k-1条边。(2)→(3)只须证T是连通图。反证法设T不连通,可以分为l个连通分图(l≥2),设第i个分图有ni个顶点,因为第i个分图是树,所以有ni-1条边,l个分图共有边数为:与已知矛盾。所以T为连通图。(3)→(4)、(4)→(5)、(5)→(6)、及(6)→(1)的证明略。定理2:图T是树,则T中的边数m等于点数n减1,即:m=n-1证明:如图图T是树,则依树的定义,则T是连通图,对于m=n-1可以用数学归纳法证明。(1)当n=1时,m=0,m=n-1成立。(2)当n=1时,m=1,m=n-1成立。(3)假设当n=k时,m=n-1成立。(4)对于k+1个顶点的图T而言,由树的性质1可知,T中至少有两个悬挂点。设v1是T的一个悬挂点,考虑图T-{v1},则图T-{v1}的顶点数为K,由归纳假设可得:,因为,,则,证毕。证明:必要性因T是连通的,故任两个点之间至少有一条链。但如果某两个点之间有两条链的话,那么图T中含有圈,这与树的定义矛盾,从而任两个点之间恰有一条链。充分性设图T中任两个点之间恰有一条链,那么易见T是连通的,如果T中含有圈,那么这个圈上的两个顶点之间有两条链,这与假设矛盾,故T不含圈,于是T是树。定理3:图T是树的充分必要条件是任意两个顶点之间恰有一条链。(1)T是无圈图(2)T是连通图(3)T中边数为点数减1,即(4)T中减去一条边则不连通(5)T中加一条边则恰有一个圈(6)T中至少有两个悬挂点根据树的定义及其三个性质的证明,我们可以归纳出树T的六个基本性质,即:二、图的支撑树定义2设图T=[V,E’]是图G=(V,E)的支撑子图,如果T是一个树,则称T是G的一个支撑树。v1v3v2v4v5v6(a)v3v1v2v4v5v6(b)(b)是(a)的一个支撑树。