티스토리 뷰
트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다:
1. 트리에서 임의의 정점 $x$를 잡는다.
2. 정점 $x$에서 가장 먼 정점 $y$를 찾는다.
3. 정점 $y$에서 가장 먼 정점 $z$를 찾는다.
트리의 지름은 정점 $y$와 정점 $z$를 연결하는 경로다.
증명) 트리에서 정점 $u$와 정점 $v$를 연결하는 경로가 트리의 지름이라고 가정하자. 임의의 정점 $x$를 정하고, 정점 $x$에서 가장 먼 정점 $y$를 찾았을 때, 아래와 같이 경우를 나눌 수 있다.
i. $x$가 $u$ 혹은 $v$인 경우
ii. $y$가 $u$ 혹은 $v$인 경우
iii. $x$, $y$, $u$, $v$가 서로 다른 경우
자명하게 i., ii.에 대해서 위 알고리즘이 트리의 지름을 올바르게 구한다는 것을 알 수 있다. 이제 iii. 경우에 대해서 알고리즘이 트리의 지름을 올바르게 구한다는 것을 증명하면 된다. iii. 경우일 때 아래와 같이 두 가지 경우가 가능하다.
a. 정점 $x$와 정점 $y$를 연결하는 경로가 정점 $u$와 정점 $v$를 연결하는 경로와 한 점 이상 공유하는 경우
b. 정점 $x$와 정점 $y$를 연결하는 경로가 정점 $u$와 정점 $v$를 연결하는 경로와 완전히 독립인 경우
$d(s, t)$를 트리에서 정점 $s$와 정점 $t$의 거리라고 하자. a.의 경우 아래 그림에서 $d(t, y) = \max(d(t, u), d(t, v))$라는 것을 알 수 있다. 때문에 위 알고리즘은 트리의 지름을 올바르게 구한다.
b.의 경우 아래 그림과 같은 상황이 된다는 것인데 $u$에서 제일 먼 점이 $v$가 아니라 $y$가 되어 $u$와 $v$를 연결하는 경로가 트리의 지름이 된다는 가정에 모순된다. 때문에 b.의 경우는 불가능하다는 것을 알 수 있다.
때문에 소개한 알고리즘은 트리의 지름을 올바르게 구한다는 것을 증명했다.
'공부' 카테고리의 다른 글
Li Chao Tree (Dynamic Convex Hull Optimization) (0) | 2021.03.08 |
---|---|
Stern-Brocot 트리 (0) | 2019.05.21 |
트리의 지름 구하기 (5) | 2016.10.11 |
Convex Hull Optimization (4) | 2016.08.23 |
가장 먼 두 점 구하기 (6) | 2016.07.17 |
Building Heap in Linear Time (2) | 2016.07.01 |
-
명우님의 팬 이게 바로 빌라봉에서 봤던 그것이었군요! 2019.09.29 22:00
-
pica4500 d(t,y)=max(d(t,u),d(t,v)) 이 부분이 잘 이해가 안가는데
d(t,y)>=max(d(t,u),d(t,v)) 이 식은 나올 수 없나요? 제가 생각해봤을 때, x-t-y가 트리의 지름이라고 가정하면 d(t,y)가 더 크게 나와야하는것 아닌가 싶어서요 2020.09.15 22:17 -
전명우 네, 맞습니다. 그래서 v가 u에서 제일 먼 점이라는 가정에 모순이 생겨 귀류법으로 증명됩니다. 4년 전에 쓴 글이라 무슨 생각으로 저렇게 썼는지 잘 기억 안 나네요.. 2020.09.26 18:59 신고
-
신응석 문득 트리 지름을 어떻게 증명했었는지 그 흐름이 잘 기억이 안나 구글링하다가 여기로 안착.. 증명 깔끔하네요. 잘 보았어요. ^^ 안부는 덤. 2021.07.20 09:45
-
전명우 안녕하세요. 신 프로님. 오랜만입니다ㅎㅎ 이렇게 보니 반갑습니다. 잘 지내시는지요~ 2021.08.30 12:09 신고
- Total
- 227,241
- Today
- 102
- Yesterday
- 92
- ioi
- IOI2014
- majority
- dynamic programming
- z-trening
- Dynamic Pramming
- Boyer-Moore Majority Vote Algorithm
- TRIE
- IOI2011
- BOI 2001
- Tree
- optimization
- Segment tree
- Divide & Conquer
- BOI
- IOI2012
- Dijkstra
- Boyer
- Splay Tree
- USACO
- HackerRank
- moore
- Knuth Optimization
- idea
- Greedy Method
- Algorithm
- IOI2013
- BOI 2009
- vote
- Parametric Search