Dual of Planar Graph, min-cut → shortest path
평면 그래프의 쌍대로 가면 min-cut 이 shortest path 가 된다. 면을 정점으로, 면 공유 간선을 dual 간선으로 변환하면 O(V² E) 흐름을 O((V+E) log V) 다익스트라로 해결.
메타데이터
| ID | dual-of-planar-graph |
| 카테고리 | algorithm |
| 버전 | v4 |
| 길이 | 12.0s (12000ms) |
| 구성 | 25 elements · 4 chapters · 4 effects |
| 태그 | #algorithm #graph #planar-graph #dual |
본문에 삽입
```anim:dual-of-planar-graph
{}
```