[문제해결기법] 9. Flow Networks

 

Flow Networks

• 가중그래프 G (모든 가중치는 양수)
• 에지의 가중치 = c(e)
• 시작점 s에는 들어오는 에지 없고, 도착점 t에는 나가는 에지가 없다
• Flow : 이용가능한 용량을 기반으로, 간선을 따라 이동하는 값
  • 모든 에지에 대해서, 0 ≤ f(e) ≤ c(e)
  • flow 값 ( |f| )은 s에서 나가는 플로우 총량 = t로 들어오는 플로우 총량

최대 플로우 = 최소 cut

컷(cut)

• 주어진 노드 V를 두 집합으로 분할
• 컷 X에 대해서, f(X)는 X를 지나는 flow 총량
• c(X)는 X를 지나는 에지의 c값 총량

최대 플로우 구하기

 

1. Ford-Fulkerson algorithm
   1. s→t 경로를 찾는다. BFS 진행
   2. 각 경로의 c(e) 최솟값을 m이라고 하자
   3. 각 경로의 에지마다, c(e) -= m으로 갱신. 반대방향 에지는 c(e’) += m으로 갱신
   4. 끝날때까지 반복 → 순방향 용량이 꽉 찼거나, 역방향의 유량이 0일 때 진행 불가

   int fordFulkerson(int graph[V][V], int s, int t){
   	while (bfs(rGraph,s,t,parent)){ // bfs로 경로탐색 진행
   		// 경로마다 가중치 최솟값 찾기 (반복문 1)
   		// 경로 에지마다 -m, 반대방향 에지는 +m (반복문2)
   		max_flow += path_flow;
   	}
   }
   

   • 응용 : m명이 n자리의 일에 지원할때, 1인 1업무라면 최대 몇명의 사람에게 일을 줄 수 있는가?(2) dfs를 이용한 백트래킹을 진행한다.
   • (1) 주어진 그래프에 s, t를 추가하고 모든 에지는 가중치가 1이라고 가정한다. 이후 그래프의 최대 플로우를 찾으면 된다.
2. Dinitz algorithm
   1. Edmonds-Karp(폴드포커슨 알고리즘을 매번 최단경로로 적용) 방법과 비슷하지만, 경로 하나를 찾는게 아니라 BFS로 가장 짧은 모든 경로를 찾는다. (에지>0)
   2. 각 경로마다 c(e)의 최솟값을 m이라 하고, 각 에지마다 c(e)-=m으로 갱신한다. 또한, 반대방향의 에지는 c(e’)+=m으로 갱신
   3. 끝날때까지 반복