ps:트리의_지름
트리의 지름
- 참고
- 먼저 관련된 텀들을 정의해야 한다.
- 트리뿐 아니라 일반 그래프에서도 똑같이 정의되는 텀들이다.
- 노드 v의 이심률(eccentricity of v): v와 다른 노드들 까지의 거리중 가장 긴 거리. (=v에서 가장 멀리 떨어진 노드까지의 거리)
- 그래프가 연결그래프가 아닌 경우에는, 모든 노드의 이심률이 무한대로 정의된다
- 그래프의 지름(graph diameter): 이심률의 최댓값 (= 이심률이 최대인 노드에서의 이심률)
- 그래프에서 가장 멀리 떨어저있는 두 노드 사이의 거리
- 그래프의 반지름(graph radius): 이심률의 최솟값 (= 이심률이 최소인 노드에서의 이심률)
- 그래프의 중심에서 가장 멀리 떨어진 노드까지의 거리
- 그래프의 중심 (center of graph): 이심률이 그래프의 반지름과 같은 노드들
- 가장 멀리 떨어진 노드까지의 거리가 최소인 노드들
- 그래프는 중심을 여러개 가질수도 있다.
- 센트로이드(Centroid)와는 다른 개념이다!
트리의 지름을 구하기
음수 가중치가 없는 경우
- 대부분의 여기에 해당한다.
- 일반적으로는 두번의 DFS 로 구하는 방법이 가장 빠르고 간단하다.
- 알고리즘은
- 1. 임의의 노드에서 DFS를 돌려서 가장 멀리 떨어진 노드 a를 찾는다
- 2. a에서 DFS를 돌려서 가장 멀리 떨어진 노드 b를 찾는다.
- 3. dist(a,b)가 트리의 지름이 된다(!)
- 시간복잡도는 O(n).
- 증명은 위의 링크들을 참고하고.. 여기서 기억해야 될 특성은, 임의의 노드에서 가장 멀리 떨어진 노드는, 그래프의 지름을 이루는 두 노드들 중 하나가 된다는 것이다.
음수 가중치가 있는 경우
- 트리에 음수 가중치가 있는 경우에는 위의 방법으로 불가능하다. 트리 DP를 사용해서 구할수 있다
- 사실 음수 가중치가 있는 트리에서 지름을 구하라는 문제를 접한적이 없어서, 실제로 구현해본적도 없다.
트리의 반지름을 구하기
- 먼저 알고 있어야 할 성질은, 트리의 반지름은 항상 트리의 지름에 포함된다는 것이다.
- dist(u,v)가 트리의 지름이라면, u→v 경로 안의 노드들 중에 트리의 중심 r이 존재하고, 트리의 반지름은 max(dist(r,u), dist(r,v))가 된다.
- 트리의 중심이 여러개여도 마찬가지. 모두 다 u→v 경로 안에 들어간다.
- 거리가 지름과 같은 노드쌍이 여러개일 수도 있다. 그러한 경로들이 모두 겹치는 구간 안에 트리의 중심이 존재한다.
- 이제 저 성질을 이용해서 u→v 경로 안의 노드들 중에서 중심과 반지름을 구하면 된다.
- dist(u,v)가 트리의 지름일때, 반지름을 구하기 위해서는 dist(u,X)과 dist(v,X)가 필요한데, 지름을 구하는 과정에서 이미 dist(u, X)는 모두 구했을것이고, dist(v,X) = dist(u,v) - dist(u,X) 이므로 따로 구할 필요가 없다.
ps/트리의_지름.txt · 마지막으로 수정됨: 2024/01/09 15:17 저자 teferi
토론