[알고리즘] 트리의 지름 증명

링크의 글을 보충 설명한 글입니다.

트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다:

1. 트리에서 임의의 정점 x를 잡는다.
2. 정점 x에서 가장 먼 정점 y를 찾는다.
3. 정점 y에서 가장 먼 정점 z를 찾는다.

트리의 지름은 정점 y와 정점 z를 연결하는 경로다.

증명) 트리에서 정점 u와 정점 v를 연결하는 경로가 트리의 지름이라고 가정하자. 임의의 정점 x를 정하고, 정점 x에서 가장 먼 정점 y를 찾았을 때, 아래와 같이 경우를 나눌 수 있다.

1. x가 u 혹은 v인 경우
2. y가 u 혹은 v인 경우
3. x, y, u, v가 서로 다른 경우

자명하게 1., 2.에 대해서 위 알고리즘이 트리의 지름을 올바르게 구한다는 것을 알 수 있다. 이제 3. 경우에 대해서 알고리즘이 트리의 지름을 올바르게 구한다는 것을 증명하면 된다. 3. 경우일 때 아래와 같이 두 가지 경우가 가능하다.

(a) 정점 x와 정점 y를 연결하는 경로가 정점 u와 정점 v를 연결하는 경로와 한 점 이상 공유하는 경우

(b) 정점 x와 정점 y를 연결하는 경로가 정점 u와 정점 v를 연결하는 경로와 완전히 독립인 경우

(a)의 경우를 살펴보자. 그림으로 나타내면 다음과 같다.

x애서 가장 먼 정점이 y이므로 $(t,y)$는 $(t,u), (t,v)$보다 크다. 수식으로는 $(t,y) > max( (t,u), (t,v) )$라고 쓸 수 있다.
$(u,v) = (u, t) + (u, v)$는 지름이다. 그런데 새로운 경로 $(t,y) + max((t,u), (t,v))$를 생각해보자. 지름보다 해당 경로가 더 길다는 결론이 나오고, 이는 $(u,v)$가 트리의 지름이라는 가정에 모순이다.

b.의 경우 아래 그림과 같은 상황이 된다는 것인데 u에서 제일 먼 점이 v가 아니라 y가 되어 u와 v를 연결하는 경로가 트리의 지름이 된다는 가정에 모순된다. 때문에 b.의 경우는 불가능하다는 것을 알 수 있다.

때문에 소개한 알고리즘은 트리의 지름을 올바르게 구한다는 것을 증명했다.

출처: https://blog.myungwoo.kr/112 [PS 이야기:티스토리]