Unit Network

최종 수정:

1정의

모든 간선 용량이 1이고 ∀v ∈ V\{s,t}: in-deg(v) = 1 또는 out-deg(v) = 1인 네트워크를 단위 네트워크라 한다. 이분 그래프 매칭 네트워크가 대표적인 예다.

2시간 복잡도

단위 네트워크에서 Dinic 알고리즘의 시간 복잡도는 O(m√n)이다.

3증명

3.1보조 정리 1

단위 네트워크의 잔여 그래프는 단위 네트워크이다.

임의의 s-t 경로를 따라 유량 1을 보낼 때, 경로 위의 임의의 중간 정점 v에서 진입 간선 (u,v)가 포화되어 사라지고 역방향 간선 (v,u)가 생성되며, 진출 간선 (v,w)가 포화되어 사라지고 역방향 간선 (w,v)가 생성된다. v의 잔여 in-deg와 out-deg는 각각 1씩 감소 후 1씩 증가하여 불변이다. 경로 밖의 정점은 영향받지 않는다. 따라서 잔여 그래프에서도 ∀v ∈ V\{s,t}: in-deg(v) = 1 또는 out-deg(v) = 1이 유지된다. ■

3.2보조 정리 2

단위 네트워크에서 Dinic의 단계 수는 O(√n)이다.

⌊√n⌋단계 이후 잔여 그래프의 최대 유량을 Fr이라 하자. 보조 정리 1에 의해 잔여 그래프도 단위 네트워크이므로, Fr을 흐름 분해하면 각 경로가 임의의 중간 정점 v를 지나는 유량은 1을 초과할 수 없다. (in-deg(v) = 1이면 v로 들어오는 용량 ≤ 1, out-deg(v) = 1이면 나가는 용량 ≤ 1.) 따라서 경로들은 중간 정점 분리이다.

⌊√n⌋단계 이후 최단 경로 길이 ≥ ⌊√n⌋ + 1이므로 각 경로는 중간 정점을 ≥ ⌊√n⌋개 포함한다. 중간 정점 총 수 ≤ n − 2이므로 Fr ≤ (n − 2)/⌊√n⌋ ≤ √n + 1이다.

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

단위 용량이므로 차단 유량은 O(m)에 구할 수 있고, 보조 정리 2에 의해 단계 수 O(√n)이므로 전체 시간 복잡도는 O(m√n)이다.