Unit Capacity Graph

1정의#

모든 간선 용량이 1인 네트워크를 단위 용량 그래프라 한다.

2시간 복잡도#

단위 용량 그래프에서 Dinic 알고리즘의 시간 복잡도는 O(m^3/2)이다.

3증명#

3.1보조 정리 1#

단위 용량 그래프에서 Dinic의 단계 수는 O(√m)이다.

⌊√m⌋단계 이후 잔여 그래프의 최대 유량을 F_r이라 하자. F_r의 유량을 흐름 분해하면 각 경로의 길이 ≥ ⌊√m⌋ + 1이다. 단위 용량이므로 잔여 그래프의 모든 간선 용량은 1이고, 같은 간선을 여러 경로가 공유할 수 없다. F_r개의 경로 각각의 길이가 ⌊√m⌋ + 1 이상이므로, m ≥ F_r · (⌊√m⌋ + 1)이고 F_r ≤ m/(⌊√m⌋ + 1) ≤ √m.

초기 ⌊√m⌋단계 이후의 각 단계에서는 유량 ≥ 1을 보내므로 단계 수 ≤ ⌊√m⌋ + √m = O(√m). ■

---

단위 용량 레벨 그래프에서는 모든 간선이 한 번만 사용되므로 차단 유량을 O(m)에 구할 수 있고, 보조 정리 1에 의해 단계 수 O(√m)이므로 전체 시간 복잡도는 O(m^3/2)이다.