트리의 지름

트리에서 두 정점을 잇는 경로 중 가장 큰 가중치(긴 거리)를 갖는 경로를 트리의 지름이라고 한다.

이는 트리에서 임의의 정점을 택하고, 해당 정점에서 가장 멀리 떨어진 정점 w를 찾고, 다시 정점 w에서 가장 멀리 떨어진 정점 d를 찾으면 쉽게 구할 수 있다.

p는 점 또는 선이다.

x에서 가장 멀리 떨어진 정점 w가

1. w일 경우:  d, w는 트리 내에서 가장 멀리 떨어진 점이므로 다음으로 찾을 정점은 d가 될것이다.

2. d일 경우: 상동.

3. d, w가 아닌 다른 정점 y일 경우: a, b사이의 거리를 d(a, b)라 할때, d(y, p) > d(d, p), d(w, p)가 되므로 y가 트리의 지름에 속해야 옳다.