티스토리 뷰

공부

트리의 지름 (Diameter of tree)

구사과 2014. 11. 1. 00:44

트리에서 정점 두개를 잡고, 거리를 재본다.

n^2 쌍의 개수만큼 거리들이 나올텐데...

이 중 가장 거리가 긴 놈을 트리의 지름이라 부른다.


dfs 2번 돌려서 O(n)에 해결할 수 있다.

알고리즘 문제 해결 전략을 학교에 두고와서 (...) 인터넷에서 직접 찾아봤는데, 책에 있는 것보다 훨씬 우아하고 간결한 알고리즘이 존재했다!!


1. 아무 점이나 잡고(루트), 이 점에서 가장 거리가 먼 점 t를 잡는다.

2. t에서 가장 거리가 먼 점 u을 찾는다.

3. t - u가 트리의 지름. 끗



여기까지는 좋은데 이를 어떻게 증명하는지가 문제다.

인터넷에서 대강 주워들은 걸로 혼자 증명해 보려고 한다. 막가는 증명이니까 믿거나 말거나...


일단 루트에서 가장 거리가 먼 점 t가 만약 지름 안에 있다면, 그 점에서 가장 거리가 먼 점인 u까지의 경로가 지름이라는 것은 자명하다.

그래서 루트에서 가장 거리가 먼 점이 지름 안에 없다는 게 모순이라는 것을 보이면 된다. (귀류법)


루트를 1이라 두고 루트에서 가장 거리가 먼 임의의 점을 x라 두고 증명해보자.


Case 1 : t - u랑 1 - x랑 겹친다.

둘의 겹치는 부분을 p - q라고 하자.

그러면

(u) - (p) - (q) - (t)

_______|_____|______

______(1)___(x)______

OR

(t) - (p) - (q) - (u)

_______|_____|______

______(1)___(x)______


대략 이런 식으로... 트리가 생길 건데,

첫번째는 d(1,t) < d(1,x) 이다.

고로 d(q,t) < d(q,x) 이고, 이 때 d(u,t)보다 d(u,x)가 더 길어지니까 d(u,t)는 지름이 아니고 모순.


두번째에서도 d(1,t) < d(1,x) -> d(p,t) < d(p,x)이다.

그런데 d(p,u) < d(p,t)이다. 그래서 d(p,u) < d(p,t) < d(p,x)이다.

이 때 d(t,u) < d(t,x)이므로 역시 모순.


Case 2 : t - u랑 1 - x랑 안 겹친다.

1 - t와 t - u랑 겹치는 점을 p라고 두고, 1 - x와 1 - t랑 가장 마지막으로 겹치는 점 (LCA)를 q라고 두자.


(1) - (q) - (p) - (t)

_______|_____|______

______(x)___(u)______

역시...

이때 d(p,u) < d(p,t)이며 d(q,t) < d(q,x)이다.

d(q,u) < d(q,t) < d(q,x)인 것도 알 수 있다.

고로, d(t,x) > d(t,q) + d(q,u) > d(t,u) + 2 * d(p,q) 이다.

역시 d(t,u) 보다 긴 간선이 있으니 모순.


코드는 생략.

댓글
댓글쓰기 폼
공지사항
Total
454,767
Today
56
Yesterday
408