지름 구하는 방법

정점이 개 있는 트리에서 지름을 찾는 간단한 방법은 다음과 같다.

1. 아무 정점 에서 DFS를 수행한다.
2. 그 결과 가장 멀리 있는 정점을 라고 한다.
3. 다시 정점 에서 DFS를 수행한다.
4. 이 DFS에서 가장 멀리 있는 정점을 라고 한다.
5. 이때 경로 는 지름입니다.

트리 = 지름의 간선 + 포레스트

위 알고리즘을 증명하기에 앞서, 트리의 구조를 분석해 보자. (지름을 언급하긴 하지만, 가 실제 지름이라는 사실은 아직 증명하지 않는다.)

예를 들어, 정점 에서 DFS를 시작해 가장 먼 정점을 , 그리고 그로부터 가장 먼 정점을 이라 하자.

이제 지름 경로를 선형으로 표현하고, 지름 경로의 간선을 제거한다고 상상하면 여러 개의 트리로 구성된 포레스트_forest가 된다. 각 트리를 지름 경로 위에 있는 정점 중 하나를 루트로 하여 구성해 보자. 이때 각 요소의 높이, 즉 루트로부터 가장 먼 정점까지의 거리는 얼마일까?

정점 가 포함된 요소의 루트를 라고 하고, 구간에 있는 어떤 요소의 루트를 , 그 안의 정점을 라고 하자.

에서 가장 먼 정점이 임을 이용하면 다음이 성립한다.

즉, 지름의 왼쪽 절반에 있는 요소()는 그 루트가 에서 떨어진 거리보다 큰 높이를 가질 수 없다.

같은 방식으로, 오른쪽 절반()에 대해서도 가 로부터 가장 멀다는 사실을 이용해 동일한 주장을 할 수 있다.

각 정점에서 가장 먼 정점

각 정점 에 대해, 가 최대가 되는 정점 를 찾아보자.

가 지름이라는 증명

이제 가 실제로 지름임을 증명해보자.

임의의 지름 가 존재한다고 가정하자. 그러면 다음 중 하나가 성립한다.

일반성을 잃지 않고 라고 가정하면,

따라서 도 지름이다.

관찰

이 알고리즘은 양의 가중치를 가진 트리에도 적용 가능하다. (여태껏 우린 가중치가 1이라는 사실을 이용한 적이 없다.) 하지만, 일반적인 그래프에서는 적용할 수 없다.