[生活]树的直径
树的直径
树的直径.txt
为了阐述清楚证明,首先作如下严格定义:
1。我们用a,b
示树中任意两个结点a,b之间的唯一路径,a,b之间可以有0个或多个结点
;用x \in a,b表示结点x处于路径a,b上,即存在形如a,x,b的路径(这里x可以和a或b
重合);用符号a-b表示a,b直接相邻。 2。结点之间的距离——根据树的性质,任意两个结点u,v之间都有唯一的路径u,v相连,
u,v上边的数目称为u,v之间的距离,记作d(u,v);
3。树的直径——树中距离最大的两个结点之间的距离称为树的直径;
4。祖先——设r是树T的根,u是T的结点,如果 x \in r,u,则x称为u的祖先;
5。公共祖先 —— 如果结点x即是u的祖先,也是v的祖先,则x是u,v的公共祖先;
6。最近公共祖先 —— 如果x是u,v的公共祖先,且对于u,v的任何其他公共祖先y都有d(x
, u) <= d(y, u),则x称为u,v的最近公共祖先。用f(u,v)表示u和v的最近公共祖先。
引理1:树的直径一定等于某两个叶结点之间的距离。
证明:trivial.
引理2:对于树中任意三个不同的结点a,b,c,满足三角不等式d(a,b) <= d(a,c) + d(c,b
)。
证明:设a,c上的结点依次为p[1], p[2], ..., p[m],设a,b上的结点依次为q[1], q[2
], ..., q[n]。其中p[1] = q[1] = a, p[m]=c, q[n]=b。
case 1: 若存在一个k,k < m 且k < n,满足 p[k+1] <> q[k+1]
且对于所有的i <= k,都
有p[i] = q[i]。
假设存在x, y > k+1且p[x] = q[y],则 p[k]-p[k+1],p[x]和q[k],q[k+1],q[y] 构成
了一个圈(因为p[k]=q[k],p[k+1]<>q[k+1]且p[x]=q[y]),这和树的性质矛盾。所以一定
不存在这样的x,y。因此,子路径p[k+1],c和q[k+1],b没有任何公共点。下面用x表示点
p[k]和q[k],于是a,b,c构成了下述形式的路径
c
|
a,x,b
于是有
d(a,c) = d(a,x) + d(x,c),
d(a,b) = d(a,x) + d(x,b),
d(c,b) = d(c,x) + d(x,b),
所以
d(a,c) + d(c,b) = d(a,x) + d(x,c) + d(x, c) + d(x,b) = d(a,b)
+ 2*d(x,c) >= d(
a,b)
定理成立;
case 2: 假设这样的k不存在。
case 2.A 若m <= n,则对于所有的i=1..m,都有p[i]=q[i],于
是点p[m]=c=q[m],即c
\in a,b。显然
d(a,b) = d(a,c) + d(c,b),
定理成立。
case 2.B 若m > n,则对于所有的i=1..n,都有p[i]=q[i],于是点q[n]=b=p[b],即b
\in a,c。显然
d(a,c) = d(a,b) + d(b,c)
即 d(a,b) = d(a,c) - d(b,c) <= d(a,c) + d(c,b)
定理也成立。
综上所述对于所有情况定理都成立。Q.E.D.
下面是引理2的另一种证明法:
设r是树的根,我们通过对树的结点数目n作归纳来证明d(a,b) <= d(a,r)+d(r,b)。
当n = 3的时候,穷举一下树的几种结构可知定理成立;
假设该定理对于所有的结点数目小于等于n的树都成立,则对于结点数目为n+1的树T,设其
根节点为r,r的子树为T[1], T[2],..,T[m]。 case 1: 若a,b属于r的两棵不同的子树,则r \in a,b,显然有d(a,b) = d(a,r) + d(r,
b);
case 2: 若a,b属于r的同一棵子树,不妨设同属于T[i]。设T[i]的根为x。则因为子树T[i
]的结点数目小于等于n,根据归纳假设有d(a,b)<=d(a,x)+d(x,b)。又因为显然有 d(a,r)
= d(a,x)+d(x,r) = d(a,x)+1,d(r,b)=d(r,x)+d(x,b)=1+d(x,b),所以有d(a,b)<=d(a,
r)+d(r,b),2成立。
综上所述,对于所有的n,在结点数目为n的树中,总是有d(a,b)<=d(a,r)+d(r,b)成立。
根据树的性质,任何一个结点都可以看作根结点,所以对于任何的结点a,b,c,如果把c看
作根节点,则有d(a,b)<=d(a,c)+d(c,a)。 Q.E.D.
引理3:设对于树中任意两个节点a,b,设x = f(a,b),则 x \in a,b。
证明:假设存在一个节点y \in x,a,使得 y <> x 且 y \in x,b。设r是树的根节点。
则存在路径 r,x,y,a 和 r,x,y,b,于是y是a,b的公共祖先,且y到a的距离比x到a的
距离近,这和x = f(a,b)矛盾。
所以假设不成立。换句话说,x,a和x,b的唯一公共点是x。所以
b。 Q.E.D. x \in a,
引理4: 设a,b,c是树中任意三个不同的结点,设x = f(f(a,b), c),即x是a,b,c三个点的
最近公共祖先,则x \in c,a 或 x \in c,b。
证明:设r为树的根。设f(a,b)=y,则x = f(y, c)。根据引理3知存在路径r,x,c和r,x
,y,且x,c和x,y只有一个公共点x。即构成形如
r
o
|
|
o x
/ \
/ \
c o o y
的路径。
首先,根据y=f(a,b),可知y,a和r,y不会有除了y以外的其他公共点,否则,假设它们的
公共点为t,则r,t和t,a构成了路径r,t,a,且y不在其上,这和y是a的祖先矛盾。因此
r,y和y,a没有除了y以外的其他公共点,即x,y与y,a不会有除了y以外的其他公共点。
同理可知x,y和y,b不会有除了y以外的其他公共点。
case 1: 若y,a和c,x没有公共点,则y,a和c,x,y除了y以外没有任何其他公共点,于
是连接c,x,y和y,a可以得到一条路径c,x,y,a,即 x \in c,a;
case 2: 若y,b和c,x没有公共点,同理可知x \in c,a;
case 3: 若y,a与c,x有公共点且y,b与c,x有公共点。不妨设y,a与c,x的公共点为z。
如果x <> y,则y,x,z,c和y,z,a可构成一个圈,和树的性质矛盾,所以这时必然有x
= y。如果z和x之间还有其他的结点,比如结点z',且z'不在y,a上,则x,z',z,c和y
,z,a (注意到这时y=x)构成了一个圈。所以这种情况下,在路径c,x上x的前一个相邻
节点z一定在x,a上。同理,z一定在x,b上。即有如下形式:
r
o
|
|
o x (y)
/
z o,,,a
/ \
/ \
c o b
这时显然r,x-z,a构成一条路径,且r,x-z,b构成一条路径,所以z是a,b的公共祖先,
且d(z,a) = d(x,a)-1 < d(x,a)。这和x=y=f(a,b)矛盾。
故此情况不可能存在。
根据case 1,2,3知定理成立。 Q.E.D.
定理5: 设r是树T的根,u是距离r最远的结点,v是距离u最远的结点。则树的直径就是d(u
, v)。
证明:设a, b是除了u,v以外的另外两个叶节点。设x = f(f(a, b),
u)。即x是a,b,u三个
节点的最近公共祖先。
根据引理4,一定有 x \in u,a 或 x \in u,b。不妨设x \in u,b 成立。
于是就有u,x,b这条路径,即
d(u,b) = d(u,x)+d(x,b) ......(1) 于是
d(r,u) >= d(r,a) // 因为u是距离r最远的点
==> d(r,x) + d(x,u) >= d(r,x) + d(x,a) // 因为根据公共祖先的定义,x \in r,u
且 x \in r,a
==> d(u,x) >= d(x,a) ........(2)
于是
d(u,v) >= d(u,b) // 因为v是距离u最远的点
= d(u,x)+ d(x,b) // 根据(1)式
>= d(x,a) + d(x,b) // 根据(2)式
>= d(a,b) // 根据引理2
所以对于除了u,v外任意的叶节点a,b,总有d(u, v)>= d(a,b)。
如果a,b中有一个是u,v之一,显然也有d(u, v)>=d(a,b)。
再根据引理1和树的半径的定义,可知d(u,v)就是T的直径。 Q.E.D.