2018. 9. 24. 22:40 알고리즘&자료구조/이론
트리의 지름
트리에서 두 정점을 잇는 경로 중 가장 큰 가중치(긴 거리)를 갖는 경로를 트리의 지름이라고 한다.
이는 트리에서 임의의 정점을 택하고, 해당 정점에서 가장 멀리 떨어진 정점 w를 찾고, 다시 정점 w에서 가장 멀리 떨어진 정점 d를 찾으면 쉽게 구할 수 있다.
p는 점 또는 선이다.
x에서 가장 멀리 떨어진 정점 w가
1. w일 경우: d, w는 트리 내에서 가장 멀리 떨어진 점이므로 다음으로 찾을 정점은 d가 될것이다.
2. d일 경우: 상동.
3. d, w가 아닌 다른 정점 y일 경우: a, b사이의 거리를 d(a, b)라 할때, d(y, p) > d(d, p), d(w, p)가 되므로 y가 트리의 지름에 속해야 옳다.
'알고리즘&자료구조 > 이론' 카테고리의 다른 글
Segment tree, Lazy approch (0) | 2018.10.30 |
---|---|
Hasse diagram (0) | 2018.09.30 |
Min-max heap (0) | 2018.09.29 |
부분합 (0) | 2018.09.24 |
그래프의 표현 (0) | 2018.09.24 |