当前位置 博文首页 > Patience:树的直径 证明 算法导论
cs树的直径的定义:
树中任意两点距离的最大值
?
树的直径的求法:
从树的任意一点y,通过BFS到达终点x;则x必为直径的一个端点。再从x通过BFS到达终点z。z必为直径的另一个端点。则从x经过BFS到z的路径为树的其中一条直径。
?
证明:
?
思路:
首先利用反证法证明x为直径的一个端点,则同理z也是直径的一个端点,从而xz为树的直径。
?
证:
反证法。
假设x不为直径的一个端点。
则对于直径uv,u与v与x互异,且dis(u, v) > dis(x, z)
1. 若x在uv上:
记dis(x, y)为树中x到y的距离。由树的性质知,树的任意两点间有且仅有一条路径。则此路径既为x与y之间的最短路径,又是x与y之间的最长路径。因此,y到v之间必存在y先到达x再从x到达v的路径。
即:dis(y, x) < dis(y, x) + dis(x, v) 这与通过点y经过BFS得到x矛盾!
?
2.若x不在uv上:
分类讨论从y到x的路径是否与直径uv相交:
2.1 相交:
记与直径uv的交点为h,则有dis(u, v) = dis(u, h) + dis(h, v)
由于从y点BFS得到终点x,故而对于树上任意一点p,dis(y, x) >= dis(y, p)=>dis(y, x) >= dis(y, v) (*)代入dis(y, x) = dis(y, h) + dis(h, x), dis(y, v) = dis(y, h) + dis(h, v) 于(*)式,
则dis(h, x) >= dis(h, v)=>dis(u, h)? + dis(h, x) >= dis(u, h) + dis(h, v)=>dis(u, x) >= dis(u, v)
而由于z为从点x通过BFS得到的最远点,故而= dis(x, z) >= dis(u, x) >= dis(u, v) => dis(x, z) >= dis(u, v)
与假设dis(u, v) > dis(x, z)矛盾!
?
2.2 不相交:
对于直径uv,u到v的路径上必存在点h,使得dis(u, h) = 1
由树的定义知,y到h必然存在一条路径,且dis(x, h) = dis(x, y) + dis(y, h) >= 2
则dis(x, v) = dis(x, h) + dis(h, v) >= 2 + dis(h, v) > 1 + dis(h, v) = dis(u, h) + dis(h, v) = dis(u, v) 这与uv是直径矛盾!
?
综上所述,假设不成立,故x为直径的一个端点。
同理,从x经过BFS必然得到直径的另一个端点。
故而xz为树的其中一条直径。证毕。