트리의 지름 증명
우선 선형 시간안에 트리의 지름을 구하는 방법은 다음과 같다. 트리에서 임의의 정점 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번의 ..
알고리즘/이론
2023. 5. 20. 18:33