알고리즘/이론
트리의 지름 증명
deulee
2023. 5. 20. 18:33
우선 선형 시간안에 트리의 지름을 구하는 방법은 다음과 같다.
- 트리에서 임의의 정점 X를 정한다.
- 정점 X에서 가장 먼 정점 Y를 구한다.
- 정점 Y에서 가장 먼 정점 Z를 구한다.
즉, 트리의 지름은 정점 Y와 정점 Z 사이의 거리를 의미한다.
이를 증명하는 방법은 다음과 같다.
증명
만약 트리에서 정점 U와 정점 V를 연결하는 경로가 트리의 지름이라고 가정하자.
임의의 정점 X를 정하고, X에서 가장 먼 정점 Y를 찾았을 때, 아래와 같이 경우를 만들 수 있다.
- X가 U 혹은 V인경우
- Y가 U 혹은 V인경우
- X, Y, U, V가 서로 다른 경우
이 경우 1, 2번은 무조건 올바르게 작동할 수 밖에 없다. 그야 DFS 알고리즘에 의해서 당연히 성립될 수 밖에 없다.
그럼 문제는 3번의 경우이다.
3번의 경우 두 가지 경우의 수가 만들어진다.
1. 정점 X와 정점 Y를 연결하는 경로가 정점 U와 정점 V를 연결하는 경로와 한 정점 이상을 공유하는 경우
정보는 다음과 같다.
- 트리의 지름은 D(U, V)이다.
- 임의의 정점 X에서 가장 먼 것은 Y이다.
- D(T, Y)는 D(T, U) 또는 D(T, V)이다.
- 왜냐하면 X에서 제인 먼 거리는 Y이고 U, V는 트리의 지름이기 때문에 T에서 더 먼 정점 max(D(T, U), D(T, V))이 Y가 된다. - X는 T를 거쳐서 트리의 지름의 끝점으로 가야한다는 것
- T에서 가장 거리가 먼 점으로 가야 말이 성립이 된다.
- D(X, Y) 경로에서 T에서 가장 먼 점이 Y가 된다.
- D(U, V) 경로에서는 T에서 가장 먼 점이 U 또는 V가 된다.
- 그렇기 때문에 Y는 U 혹은 V가 된다.
2. 정점 X와 정점 Y를 연결하는 경로가 정점 U와 정점 V를 연결하는 경로와 완전히 독립인 경우
이 경우의 정보도 다음과 같다.
- D(X, Y) 입장에서는 D(A, Y) > D(A, B, V)이어야 한다.
왜냐하면 X에서 가장 먼 정점이 Y이기 때문이다. - D(U, V) 입장에서는 D(B, V) > D(B, A, Y)이어야 한다.
왜냐하면 U와 V가 트리의 지름이기 때문에 U에서 가장 먼 정점이 V이어야 하는 것이다. - 즉, D(B, V)가 D(X, Y) 입장에서는 D(B, A, Y)가 더 길어야 하는데 이는 모순을 의미한다.
그러므로 이 경우 즉, 정점 X와 정점 Y를 연결하는 경로가 정점 U와 정점 V를 연결하는 경로가 완전히 독립되는 경우는 존재할 수 없다.
이렇게 되면 어떤 임의의 정점에서 가장 먼 정점을 찾게 되고 그 정점에서 가장 먼 정점을 찾으면 그것이 트리의 지름이 된다는 것은 부정할 수 없는 이론이 된다.
출처
https://velog.io/@zioo/트리의-지름-구하기