====== 트리의 지름 ====== * 참고 * [[https://00ad-8e71-00ff-055d.tistory.com/115]] * [[https://codeforces.com/blog/entry/101271]] * 먼저 관련된 텀들을 정리해보자 * 트리뿐 아니라 일반 그래프에서도 똑같이 정의되는 텀들이다. * 노드 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를 사용해서 구할수 있다 * 방법은 [[https://00ad-8e71-00ff-055d.tistory.com/115]]을 참고 * 사실 음수 가중치가 있는 트리에서 지름을 구하라는 문제를 접한적이 없어서, 실제로 구현해본적도 없다. ===== 트리의 중심과 반지름을 구하기 ===== * 먼저 알고 있어야 할 성질은, 트리의 반지름은 항상 트리의 지름에 포함된다는 것이다. * 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) 이므로 따로 구할 필요가 없다. ===== 각 노드의 이심률과 가장 멀리 떨어져있는 노드를 구하기 ==== * u의 이심률은 u에서 가장 멀리 떨어져있는 노드까지의 거리이다. (위에도 적었지만, 잘 안쓰는 용어이다보니 까먹을까 봐 다시 한번 적는다) * 트리의 지름을 찾을 때 사용한 성질인, **임의의 노드에서 가장 멀리 떨어진 노드는, 그래프의 지름을 이루는 양 끝 노드들 중 하나가 된다**를 이용하면 방법은 직관적으로 나온다. * 트리의 지름을 찾고 -> 트리의 지름을 이루는 양 끝 노드 u, v로부터 각각 BFS를 돌려서 각 노드까지의 거리를 구해둔다. * dist(u, X)는 트리의 지름을 계산하는 과정에서 이미 구했을 것이므로, dist(v, X)만 추가로 구하면 된다 * 어떤 노드 w에서 가장 먼 노드는, dist(u, w)과 dist(v, w) 중 값이 큰 쪽에 해당되는 노드이다. * 식을 조금 바꿔서 정리하면, w의 이심률은 {w에서 중심까지의 거리} + {반지름} 이 된다고도 쓸 수 있다. * max_u(dist(w, u)) = dist(w, center) + radius