树的直径

树的直径 为了阐述清楚证明，首先作如下严格定义: 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)。