트리의 지름 구하기 [증명]

트리의 지름

트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은, 먼 두 정점을 연결하는 경로를 의미합니다.

선형 시간안에 트리에서 지름을 구하는 방법은 아래 Flow를 기억해두시면 좋습니다.

1. 트리에서 임의의 정점 x를 잡습니다.
2. 정점 x에서 가장 먼 정점 y를 찾습니다. (dfs / bfs 사용)
3. 정점 y에서 가장 먼 정점 z를 찾습니다. (dfs / bfs 재사용)

이렇게 위 flow 대로 생각하면,

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

 

여기서 이렇게하면 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 일컫게 됩니다.

 

증명을 하자면,

트리에서 정점 u와 정점 v를 연결하는 경로가 트리의 지름이라고 가정하겠습니다.

임의의 정점 x를 정하고, 정점 x에서 가장 먼 정점 y를 찾았을 때, 아래와 같은 경우를 나눌 수 있습니다.

•  x 가 u 혹은 v 인 경우
•  y 가 u 혹은 v 인 경우
•  x, y, u, v 가 서로 다른 경우

자명하게도, 1,2에 대해서는 위 알고리즘이 트리의 지름을 올바르게 구한다는 것을 알수 있습니다.

하지만 여기서 3에 대해서 증명만 하면, 더 증명하면 될 거 같습니다.

3일 경우에, 두 가지 케이스가 가능합니다.

 

 

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

d(s, t) 를 트리에서 정점 s와 정점 t의 거리라고 할 때,

d(t, y) >= max(d(t, u), d(t, v)) 라는 것을 알 수 있습니다.

* 귀류법으로 정리를 한 블로그가 많아 더 참고해서 봐도 좋을 거 같습니다.

 

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

 

u 에서 제일 먼 점이 v가 아니라, y가 되어 u와 v를 연결하는 경로가 트림의 지름이 된다는 가정에 모순됩니다.