荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: Version (Who makes history and why), 信区: Program
标 题: [转寄] 树中的最长距离的证明(from zju) readchild (转寄)[转载]
发信站: 荔园晨风BBS站 (Sun Apr 20 23:12:01 2003), 站内信件
【 以下文字转载自 Version 的信箱 】
【 原文由 pcAngel@bbs.pku.edu.cn 所发表 】
发信人: birdf (永远支持德意志), 信区: ACM_ICPC
标 题: [转寄] 树中的最长距离的证明(from zju)
发信站: 北大未名站 (2003年03月16日23:52:12 星期天), 转信
来 源: from bbs.zju.edu.cn (sg.zju.edu.cn [210.32.133.3])
日 期: Sun Mar 16 23:51:39 2003
发信人: standlove (standlove), 信区: Algorithm
标 题: Re: 树中的最长距离的证明。（上贴做废）
发信站: 浙江大学海纳百川站 (Fri Feb 28 22:31:36 2003)
呵呵， 以此贴为准， 狗狗来提提意见， 不要看到一半就跑了：）
[转贴]
发信人: starfish(金盆洗手，退隐江湖), 信区: Algorithm. 本篇人气: 27
标 题: Re: How calculate the diameter of a Tree?
发信站: 南京大学小百合站 (Wed Feb 26 14:13:04 2003)
下面是我的严格证明，不过写得比较麻烦：（ 图论里面的很多问题容易理解，但是却不容
易用语言表达清楚。
为了阐述清楚证明，首先作如下严格定义：
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。所以x \in a～b。 Q.E.D.
引理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.
--
争取下个月多做一道！ +U+U
※ 来源:．浙江大学海纳百川站 http://bbs.zju.edu.cn [FROM: standlove]
--
※ 转寄:·浙江大学海纳百川站 bbs.zju.edu.cn·[FROM: birdf]
--
※ 转载:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.212.20]
--
※ 转寄:·北大未名站 bbs.pku.edu.cn·[FROM: 210.39.3.50]
--
※ 转载:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.1.50]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店