树的直径

 

求法:1.先任意选一个点，找到离这个点距离最远的点q

2.然后以q为根，找距离q最远的点p,那么pq就是这棵树的直径了

证明:

假定st是直径，

我们需要证明的其实就是一个性质树上任意一个点x，距离x最远的点=直径的一个端点?

那么我们假定的条件就是距离x最远的点y!=直径的一个端点，

同时还要保证st是直径的性质，看这样的条件下，能否成立

 

情况1: x在直径上

sx=编号1，xt=编号2，xy=编号3

首先最远的条件是：3>1    ,    3>2

那么3+2(yt)>1+2(st),  3+1(ys)>2+1(st),那么st(1+2)就不是直径(最长边)了

情况2:x不在st上，但是xy与st相交于u

那么我们假定

su=编号1，ut编号2，yu=编号3，xu=编号4

首先最远的点的性质，3+4>1+4,3+4>2+4

那么3>1,3>2，那么根上面情况一样

那么3+2(yt)>1+2(st),  3+1(ys)>2+1(st),那么st(1+2)就不是直径(最长边)了

情况3:x不在st上，xy于st不相交

那么我们连线x到st这条边的交点为u

假定su=编号1，ut=编号2，xu=编号4，xy=编号3

首先最远点的条件 3>1+4,3>2+4

那么显而易见3>1,3>2

那么3+4+1(ys)>2+1(st) ,  3+4+2（yt）>1+2(st),  st不再是直径。