최대 유량 알고리즘 (1)
29 Nov 2017 | Max Flow Algorithm Ford-Fulkerson Algorithm Graph
이번 글에서는 최대 유량 알고리즘(Max Flow Algorithm)을 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)을 중심으로 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
최대 유량 알고리즘이란 가중치가 있는 방향그래프(directed graph) $G$와 시작(source) 노드 $s$, 도착(sink) 노드 $t$가 주어졌을 때 각 엣지의 용량(capacity)을 고려하여 $s$에서 $t$로 흘려보낼 수 있는 최대 유량(flow)을 구하는 알고리즘을 가리킵니다. 전력, 수도, 통신 등 다양한 분야에서 폭넓게 쓰이고 있습니다. 용어 및 개념 몇 가지 살펴보겠습니다.
$G$의 각 엣지 가중치를 용량(capacity)라고 하며 ($u,v$)의 용량을 $c(u,v)$라고 씁니다. 용량은 항상 0 이상입니다. 노드 $u$와 $v$ 사이를 흐르는 유량(net flow)은 $f(u,v)$라고 쓰며 유량은 실수치 함수(real-valued function)입니다. 최대 유량 문제에는 다음 세 가지 제약조건이 있습니다. 곱씹어보면 상식적인 것들입니다.
- capacity constraint : $f(u,v)≤c(u,v)$, 즉 유량은 용량을 초과할 수 없다.
- skew symmetry : $f(u,v)=-f(v,u)$
- flow conservation : 각 노드에서 유량은 새로 더해지거나 감소되지 않는다.
이번엔 그림 표기 방법을 살펴보겠습니다. 용량 정보가 $c(u,v)=10$이고 $c(v,u)=4$라면 다음과 같이 표시할 수 있습니다.
$u$에서 $v$로의 유량이 8이라면 다음과 같이 표시합니다.
$v$에서 $u$로의 유량이 3이라면 다음과 같이 표시합니다.
위 그래프를 양의 순 유량(positive net flow)으로 다시 표시하면 다음과 같습니다. 위 그래프를 아래처럼 바꾸는 과정을 cancellation이라고 합니다.
이번엔 residual network에 대해 살펴보겠습니다. $u$에서 $v$로의 residual capacity $c_f(u,v)$는 다음과 같이 정의됩니다.
\[{ c }_{ f }\left( u,v \right) =c\left( u,v \right) -f\left( u,v \right)\]
예를 들어보겠습니다. 하단 좌측과 같은 유량 그래프 $G$가 주어졌을 때 $G$의 residual network $G_f$는 하단 우측과 같습니다. $G_f$의 엣지는 cancallation 과정을 거쳐 도출된 양의 순 유량을 바탕으로 계산됩니다.
- $c_f(u,v)=c(u,v)-f(u,v)=9-4=5$
- $c_f(v,u)=c(v,u)-f(v,u)=0-(-4)=4$
augmenting path란 residual network $G_f$ 상에서 $s$에서 $t$로 가는 경로를 가리킵니다.
Ford-Fulkerson Algorithm
포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)은 residual network를 활용해 최대 유량을 구하는 기법입니다. 다음 그림과 같은 residual network $G_f$가 주어졌다고 칩시다.
우선 깊이우선탐색(DFS)이나 너비우선탐색(BFS) 방식으로 $s$에서 $t$로 가는 경로를 하나 찾습니다. 아래 예시에서는 {$s,a,b,t$}를 찾았습니다. 이 경로를 통해 흐를 수 있는 최대 유량은 1입니다.
직전 단계에서 구한 경로의 반대 방향으로 최대 유량(1)만큼을 흘려 보내는 엣지를 만들어 줍니다(augmenting path+cancellation). 다시 $s$에서 $t$로 가는 경로를 하나 찾습니다. {$s,a,t$}입니다. 이 경로를 통해 흐를 수 있는 최대 유량은 1입니다.
직전 단계에서 구한 경로의 반대 방향으로 최대 유량(1)만큼을 흘려보내는 엣지를 만들어 줍니다. 다시 $s$에서 $t$로 가는 경로를 하나 찾습니다. {$s,b,a,t$}입니다. 이 경로를 통해 흐를 수 있는 최대 유량은 1입니다.
직전 단계에서 구한 경로의 반대 방향으로 최대 유량(1)만큼을 흘려보내는 엣지를 만들어 줍니다. 다시 $s$에서 $t$로 가는 경로를 하나 찾습니다. {$s,b,t$}입니다. 이 경로를 통해 흐를 수 있는 최대 유량은 2입니다.
직전 단계에서 구한 경로의 반대 방향으로 최대 유량(2)만큼을 흘려보내는 엣지를 만들어 줍니다. 다시 $s$에서 $t$로 가는 경로를 하나 찾습니다. 그런데 이제는 $s$에서 $t$로 가는 경로가 존재하지 않습니다.
포드-풀커슨 알고리즘 수행을 종료합니다. 위 그래프는 residual network $G_f$이기 때문에, $s$에서 $t$로 향하는 최대 유량은 $a$에서 $t$의 2, $b$에서 $t$의 3, 이렇게 해서 총 5가 됩니다. 포드-풀커슨 알고리즘의 의사코드는 다음과 같습니다.
이번엔 다른 예시를 보겠습니다. 다음과 같은 유량그래프 $G$가 주어졌다고 칩시다.
위 유량그래프를 기반으로 만든 residual network $G_f$는 다음과 같습니다. $G_f$에서 $s$에서 $t$로 향하는 경로(augmenting path)를 찾습니다(BFS, DFS 등 활용). 붉은색으로 표시해 두었습니다.
이 경로를 통해 흐를 수 있는 최대 유량은 4라는 것을 확인할 수 있습니다. 경로의 반대 방향으로 최대 유량(4)만큼을 흘려보내는 엣지를 만들어 줍니다. 다음과 같습니다.
위 residual network $G_f$를 바탕으로 유량그래프 $G$를 만들면 다음과 같습니다. 아래의 유량그래프는 처음 분석을 시작한 그래프와 동치입니다.
포드-풀커슨 알고리즘은 residual network $G_f$ 상의 $s$에서 $t$로 가는 경로가 존재하지 않을 때까지 augmenting path와 cancellation을 반복적으로 수행해 줍니다.
이번 글에서는 최대 유량 알고리즘(Max Flow Algorithm)을 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)을 중심으로 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
최대 유량 알고리즘이란 가중치가 있는 방향그래프(directed graph) $G$와 시작(source) 노드 $s$, 도착(sink) 노드 $t$가 주어졌을 때 각 엣지의 용량(capacity)을 고려하여 $s$에서 $t$로 흘려보낼 수 있는 최대 유량(flow)을 구하는 알고리즘을 가리킵니다. 전력, 수도, 통신 등 다양한 분야에서 폭넓게 쓰이고 있습니다. 용어 및 개념 몇 가지 살펴보겠습니다.
$G$의 각 엣지 가중치를 용량(capacity)라고 하며 ($u,v$)의 용량을 $c(u,v)$라고 씁니다. 용량은 항상 0 이상입니다. 노드 $u$와 $v$ 사이를 흐르는 유량(net flow)은 $f(u,v)$라고 쓰며 유량은 실수치 함수(real-valued function)입니다. 최대 유량 문제에는 다음 세 가지 제약조건이 있습니다. 곱씹어보면 상식적인 것들입니다.
- capacity constraint : $f(u,v)≤c(u,v)$, 즉 유량은 용량을 초과할 수 없다.
- skew symmetry : $f(u,v)=-f(v,u)$
- flow conservation : 각 노드에서 유량은 새로 더해지거나 감소되지 않는다.
이번엔 그림 표기 방법을 살펴보겠습니다. 용량 정보가 $c(u,v)=10$이고 $c(v,u)=4$라면 다음과 같이 표시할 수 있습니다.
$u$에서 $v$로의 유량이 8이라면 다음과 같이 표시합니다.
$v$에서 $u$로의 유량이 3이라면 다음과 같이 표시합니다.
위 그래프를 양의 순 유량(positive net flow)으로 다시 표시하면 다음과 같습니다. 위 그래프를 아래처럼 바꾸는 과정을 cancellation이라고 합니다.
이번엔 residual network에 대해 살펴보겠습니다. $u$에서 $v$로의 residual capacity $c_f(u,v)$는 다음과 같이 정의됩니다.
\[{ c }_{ f }\left( u,v \right) =c\left( u,v \right) -f\left( u,v \right)\]예를 들어보겠습니다. 하단 좌측과 같은 유량 그래프 $G$가 주어졌을 때 $G$의 residual network $G_f$는 하단 우측과 같습니다. $G_f$의 엣지는 cancallation 과정을 거쳐 도출된 양의 순 유량을 바탕으로 계산됩니다.
- $c_f(u,v)=c(u,v)-f(u,v)=9-4=5$
- $c_f(v,u)=c(v,u)-f(v,u)=0-(-4)=4$
augmenting path란 residual network $G_f$ 상에서 $s$에서 $t$로 가는 경로를 가리킵니다.
Ford-Fulkerson Algorithm
포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)은 residual network를 활용해 최대 유량을 구하는 기법입니다. 다음 그림과 같은 residual network $G_f$가 주어졌다고 칩시다.
우선 깊이우선탐색(DFS)이나 너비우선탐색(BFS) 방식으로 $s$에서 $t$로 가는 경로를 하나 찾습니다. 아래 예시에서는 {$s,a,b,t$}를 찾았습니다. 이 경로를 통해 흐를 수 있는 최대 유량은 1입니다.
직전 단계에서 구한 경로의 반대 방향으로 최대 유량(1)만큼을 흘려 보내는 엣지를 만들어 줍니다(augmenting path+cancellation). 다시 $s$에서 $t$로 가는 경로를 하나 찾습니다. {$s,a,t$}입니다. 이 경로를 통해 흐를 수 있는 최대 유량은 1입니다.
직전 단계에서 구한 경로의 반대 방향으로 최대 유량(1)만큼을 흘려보내는 엣지를 만들어 줍니다. 다시 $s$에서 $t$로 가는 경로를 하나 찾습니다. {$s,b,a,t$}입니다. 이 경로를 통해 흐를 수 있는 최대 유량은 1입니다.
직전 단계에서 구한 경로의 반대 방향으로 최대 유량(1)만큼을 흘려보내는 엣지를 만들어 줍니다. 다시 $s$에서 $t$로 가는 경로를 하나 찾습니다. {$s,b,t$}입니다. 이 경로를 통해 흐를 수 있는 최대 유량은 2입니다.
직전 단계에서 구한 경로의 반대 방향으로 최대 유량(2)만큼을 흘려보내는 엣지를 만들어 줍니다. 다시 $s$에서 $t$로 가는 경로를 하나 찾습니다. 그런데 이제는 $s$에서 $t$로 가는 경로가 존재하지 않습니다.
포드-풀커슨 알고리즘 수행을 종료합니다. 위 그래프는 residual network $G_f$이기 때문에, $s$에서 $t$로 향하는 최대 유량은 $a$에서 $t$의 2, $b$에서 $t$의 3, 이렇게 해서 총 5가 됩니다. 포드-풀커슨 알고리즘의 의사코드는 다음과 같습니다.
이번엔 다른 예시를 보겠습니다. 다음과 같은 유량그래프 $G$가 주어졌다고 칩시다.
위 유량그래프를 기반으로 만든 residual network $G_f$는 다음과 같습니다. $G_f$에서 $s$에서 $t$로 향하는 경로(augmenting path)를 찾습니다(BFS, DFS 등 활용). 붉은색으로 표시해 두었습니다.
이 경로를 통해 흐를 수 있는 최대 유량은 4라는 것을 확인할 수 있습니다. 경로의 반대 방향으로 최대 유량(4)만큼을 흘려보내는 엣지를 만들어 줍니다. 다음과 같습니다.
위 residual network $G_f$를 바탕으로 유량그래프 $G$를 만들면 다음과 같습니다. 아래의 유량그래프는 처음 분석을 시작한 그래프와 동치입니다.
포드-풀커슨 알고리즘은 residual network $G_f$ 상의 $s$에서 $t$로 가는 경로가 존재하지 않을 때까지 augmenting path와 cancellation을 반복적으로 수행해 줍니다.
Comments