트리의 지름 증명

우선 선형 시간안에 트리의 지름을 구하는 방법은 다음과 같다.

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번은 무조건 올바르게 작동할 수 밖에 없다. 그야 DFS 알고리즘에 의해서 당연히 성립될 수 밖에 없다.

 

그럼 문제는 3번의 경우이다.

 

3번의 경우 두 가지 경우의 수가 만들어진다.

 

1. 정점 X와 정점 Y를 연결하는 경로가 정점 U와 정점 V를 연결하는 경로와 한 정점 이상을 공유하는 경우

출처 : https://velog.io/@zioo/트리의-지름-구하기

 

정보는 다음과 같다.

• 트리의 지름은 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를 연결하는 경로와 완전히 독립인 경우

출처 : https://velog.io/@zioo/트리의-지름-구하기

 

이 경우의 정보도 다음과 같다.

• 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/트리의-지름-구하기

트리의 지름 구하기