알고리즘 과목 최대플로우 정리

플로우 네트워크

정의
G=(V, E)는 각각의 간선 (u, v)∊ E 의 음이 아닌 용량 c(u, v)>=0 을 갖는 방향 그래프다. 플로우 네트워크에서는 두 정점을 출발지 s와 종점 t로 구분한다. 최대 플로우 문제는, 출발지 s와 종점 t를 가지는 플로우 네트워크 G가 주어졌을 때, 최대값을 가지는 플로우를 찾는 것이다.

플로우 네트워크는 다음의 3가지 성질을 만족시켜야 한다.

1) 용량 제약조건

하나의 정점에서 다른 정점으로의 플로우가 주어진 용량을 넘어서는 안 됨을 의미한다.

2) 반대칭 조건

정점 u, v에 대해 u->v  = –1 * (v->u) 이다.

3) 플로우 보존 조건

모든 정점들은 플로우 보존 조건인 들어오는 비율과 나가는 비율이 같아야 한다는 것을 의미한다.

전체가 양수인 플로우(Total Positive Flow)
정점 v로 들어가는 양의 플로우

전체의 실질적인 플로우(Total New Flow)
한 정점에서 나가는 전체의 양수인 플로우에서 그 정점으로 들어가는 전체의 양수인 플로우를 뺀 것을 의미. 즉 정점 v가 있다면 이를 기준으로 나가는 값에서 들어오는 값을 뺀 플로우의 양을 의미한다.

(플로우 네트워크의 예 : 출처=Instroduction To Algorithms)

위의 그림에서 a에서 화살표 방향이 의미하는 것은 한 정점에서 다른 정점으로 보낼 수 있는 플로우의 최대 용량을 의미한다. 그림 b는 정점 u에서 v까지 보내는 플로우의 양을 19라고 가정했을 때 양의 플로우만 그래프에 나타낸 것이다. 그림에서 / 기호는 나눗셈을 의미하지 않고 단순히 플로우와 용량을 분리하기 위해 사용되었다.

그림 b에서 한 정점에서 다른 정점으로 나가는 플로우의 양이 19이므로 시작점 s에서 다른 정점으로 나가는 플로우의 양이 11 + 8 = 19 임을 알 수 있다. 그리고 종점 t로 들어가는 플로우의 양도 15 + 4= 19 임을 알 수 있다.

중간에 있는 정점들 중에서 / 기호 없이 그냥 숫자만 표시되어 있는 것이 있다. 예를 들면 v1 –> v2는 10으로만 표시되어 있는 데 이는 v1에서 v2로 나가는 플로우의 양이 0 임을 의미한다.

s와 t 사이에 있는 모든 정점들은 플로우 보존 조건인 들어오는 비율과 나가는 비율이 같아야 한다는 것을 만족시킨다. 예를 들어 v2의 경우 들어오는 비율이 0 + 4 + 8 = 12 이고 나가는 비율 역시 1 + 11 = 12 이므로 플로우 보존 조건을 만족함을 알 수 있다.

(다중 출발지와 다중 종점의 네트워크 : 출처=Instroduction To Algorithms)

다중 출발지인 {s1, s2, s3, s4, s5} 와 다중 종착점인 {t1, t2, t3}을 하나의 출발점과 종착점을 가지는 그림 b로 바꾸는 방법은 다음과 같다.

1) 가상의 출발점 s와 가상의 종착점 t를 설정한다.

2) 가상의 출발점은 {s1, s2, s3, s4, s5} 로 향하는 무한대 용량을 가진 방향 간선을 가진다.

3) 정점 {t1, t2, t3}는 가상의 종착점인 t에 연결이 되며 이들의 용량은 무한대이다.

위에서 가상의 정점 s에서 다른 정점으로 나가는 용량과 {t1, t2, t3}에서 가상의 정점인 t로 향하는 용량은 같다.

포드 – 풀커슨 방법

포드 – 폴커슨 방법은 반복적이다. 모든 u, v에 대해 f(u, v)=0 으로 초기 플로우를 0으로 하면서 시작한다. 각각의 반복 단계에서, 우리는 출발지 s에서 도착점 t로 더 많은 플로우를 보낼수 있는 “확대 경로”를 찾아서 플로우를 이 경로에 따라서 확대함으로써 증가시킨다. 우리는 더 이상의 확대 경로를 찾을 수 없을 때까지 이 작업을 반복한다.

잔여 네트워크 (Residual Network)

직관적으로 주어진 플로우 네트워크와 플로우에 대해 잔여 네트워크는 더 많은 플로우를 허용할 수 있는 간선으로 구성되어 있다. f를 G의 플로우라 하고, 한 쌍의 정점 u, v를 고려해보자. 용량 c(u, v)를 초과하기 전에 u에서 v로 추가할 수 있는 플로우의 양을 (u, v)의 잔여용량(residual capacity)라고 한다.

예를 들어 c(u, v) = 16이고 f(u, v) = 11이면 용량 제한을 초과하기 전에 f(u, v)를 5단위 만큼 증가시킬 수 있다.

그림 a는 플로우 네트워크의 초기상태를 보여준다.

그림 b에서 어둡게 칠해진 경로는 확대경로를 의미하는 데 각각의 화살표는 잔여용량을 보여준다. 즉 예를 들어 정점 s와 v2를 보면 그림 a에서는 전체용량이 13이고 플로우가 8이었다. 이 경로에서는 13 – 8 = 5 만큼 잔여용량을 확장할 수 있으므로 정점 s –> v2는 확장가능한 잔여용량을 의미한다. 즉 그림 b는 그림 a에 대한 잔여 네트워크 그래프이며 어둡게 칠해진 확대경로를 p라고 할 때 잔여용량은 4이다. 잔여용량이 4인 이유는 확대경로의 잔여용량중에서 가장 작은 값을 선택해야 경로상에 있는 다른 정점들의 전체용량이 넘치지 않기 때문이다.

그림 c는 그래프의 플로우에서 경로 p를 잔여 용량 4만큼 확장한 결과 플로우이다.

그림 d는 그림 c로부터 유도된 잔여 네트워크이다.

위의 그래프는 단절 상태를 보여준다.  시작 정점인 S={s, v1, v} , 종료점인 T={v3, v4, t}일 때 단절 S, T를 보여준다.

(S, T)의 실질적인 플로우는 f(S, T) = 19이고 용량은 26이다.

단절이란 잔여 네트워크가 더이상 확대 경로를 가지지 않을 때만 그 플로우가 최대가 됨을 말한다. 네트워크의 최소 단절은 테으워크의 단절 중 그 용량이 최소가 되는 단절의 용량을 의미한다.

위의 그림에서 실질적인 플로우는 f(v1, v3) + f(v2, v3) + f(v2, v4) = 12 + (-4) + 11 = 19 이고

용량은 c(v1,v3) + c(v2, v4) = 12 + 14 = 26 이다.

포드 – 풀커슨 방법은 매번 반복할 때마다 어떤 확대 경로 p를 찾고 p를 따라서 플로우 f를 잔여 용량만큼 증가시킨다. 위의 코드는 간선으로 연결되어 있는 각각의 정점 u, v 쌍들의 플로루 f[u, v]를 갱신함으로써 그래프 G=(V, E)의 최대 플로우를 찾아낸다. u, v가 어떤 방향의 간선으로도 연결되어 있지 않는 경우, f[u, v]=0 이라고 암시적으로 가정한다. 용량은 그래프와 함께 주어지며 간선이 존재하지 않는 경우 c(u, v)=0 으로 가정한다.위의 코드에서 cf(p)는 경로 p의 일시적인 잔여 용량을 저장하는 변수다.

1-3 행은 플로우 f를 초기화한다.

4-8행의 while ㄹ루프는 반복해서 Gf의 확대 경로 p를 찾아 잔여 용량 cf(p)에 의해 플로우 f를 p를 따라서 증가시킨다. 더 이상의 확대 경로가 존재하지 않는 경우 플로우 f는 최대 플로우가 된다.