최대 유량 알고리즘 (2)
02 Dec 2017 | Max Flow Algorithm Ford-Fulkerson Algorithm Graph
이번 글에서는 최대 유량 알고리즘(Max Flow Algorithm)을 edge cut으로 수행하는 기법을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
최대 유량 알고리즘이란 가중치가 있는 방향그래프(directed graph) $G$와 시작(source) 노드 $s$, 도착(sink) 노드 $t$가 주어졌을 때 각 엣지의 용량(capacity)을 고려하여 $s$에서 $t$로 흘려보낼 수 있는 최대 유량(flow)을 구하는 알고리즘을 가리킵니다. 최대 유량을 edge cut으로 수행하는 기법에서 용량(capacity), 유량(flow) 등 기본적인 용어와 flow conservation 등 제약요건은 포드-풀커슨 알고리즘과 동일합니다. 추가된 내용은 다음과 같습니다.
우선 reverse edge가 존재하지 않는다고 둡니다. 예컨대 노드 $u$에서 $v$로 향하는 엣지가 있다면 $v$에서 $u$로 향하는 반대 엣지는 그래프에 없어야 합니다.
유량값(value of flow) $f$(혹은 |$f$|)는 다음과 같이 정의됩니다.
- 시작 노드 $s$에서 나가는 유량 - 시작 노드 $s$로 들어오는 유량
아래 그래프에서 $f$는 나가는 유량(3)만 있으므로 3이 됩니다.
위 그래프에 edge cut을 수행해 두 개 부분그래프로 쪼개 보겠습니다. $s$가 속한 부분그래프를 $S$, $t$가 속한 부분그래프를 $T$라고 둡니다. 이 때 $S$와 $T$ 사이의 순 유량(net flow) $f$와 용량 $C$는 각각 다음과 같이 정의됩니다.
\[\begin{align*}
f\left( S,T \right) &=\sum _{ u\in S }^{ }{ \sum _{ v\in T }^{ }{ f\left( u,v \right) } } -\sum _{ u\in S }^{ }{ \sum _{ v\in T }^{ }{ f(v,u) } } \\ c\left( S,T \right) &=\sum _{ u\in S }^{ }{ \sum _{ v\in T }^{ }{ c\left( u,v \right) } }
\end{align*}\]
예를 들어보겠습니다. 아래 그래프를 빨간색 선을 따라 edge cut을 수행했다고 칩시다. $f(S,T)$는 $S$에서 $T$로 가는 유량을 $T$에서 $S$로 가는 유량을 빼서 구하므로 4-1=3이 됩니다. $c(S,T)$는 $S$에서 $T$로 가는 용량만을 따지므로 2+3=5가 됩니다.
이번엔 파란색 선을 따라 edge cut을 수행했다고 칩시다. $f(S,T)=4-1=3$입니다. $c(S,T)=3+3=6$입니다.
정리 및 증명
edge cut으로 최대 유량을 구하는 데 있어 두 가지 중요한 정리가 있습니다. 첫번째는 어떻게 cut을 하더라도 유량값($f$)은 동일하다라는 사실입니다. (fot any cut ($S,T$), $f(S,T)=$|$f$|) 위 그림 예제로 설명해 보자면 빨간색 선을 따라 cut을 하든, 파란색 선을 따라 cut을 하든 $f$는 3으로 같습니다. 이는 다른 선을 따라 cut을 해도 마찬가지입니다.증명은 다음과 같습니다.
두번째 중요한 정리는 $S$와 $T$를 어떻게 자르든 $S,T$ 사이의 유량은 용량보다 작다는 것입니다. (The value of any flow)≤capacity of any cut)
algorithm
이같은 사실을 활용해 우리는 모든 가능한 경우에 대해 edge cut을 수행한 뒤 그 가운데 가장 작은 용량(capacity)을 선택하면 그것이 전체 그래프의 최대 유량이 됨을 알 수 있습니다. 위 그림 예제로 설명해보자면, 빨간색 선으로 잘라보고, 파란색 선으로 잘라보고, 다른 모든 가능한 경우의 수에 대해 잘라봐서 $c(S,T)$ 값을 각각 구하고, 이 가운데 가장 적은 값을 최대 유량으로 반환하는 겁니다. 한편 만일 최소 비용으로 그래프의 최대 유량을 높이고 싶다면 가장 적은 $c(S,T)$에 대응하는 엣지들의 용량을 높여주면 됩니다.
이번 글에서는 최대 유량 알고리즘(Max Flow Algorithm)을 edge cut으로 수행하는 기법을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
최대 유량 알고리즘이란 가중치가 있는 방향그래프(directed graph) $G$와 시작(source) 노드 $s$, 도착(sink) 노드 $t$가 주어졌을 때 각 엣지의 용량(capacity)을 고려하여 $s$에서 $t$로 흘려보낼 수 있는 최대 유량(flow)을 구하는 알고리즘을 가리킵니다. 최대 유량을 edge cut으로 수행하는 기법에서 용량(capacity), 유량(flow) 등 기본적인 용어와 flow conservation 등 제약요건은 포드-풀커슨 알고리즘과 동일합니다. 추가된 내용은 다음과 같습니다.
우선 reverse edge가 존재하지 않는다고 둡니다. 예컨대 노드 $u$에서 $v$로 향하는 엣지가 있다면 $v$에서 $u$로 향하는 반대 엣지는 그래프에 없어야 합니다.
유량값(value of flow) $f$(혹은 |$f$|)는 다음과 같이 정의됩니다.
- 시작 노드 $s$에서 나가는 유량 - 시작 노드 $s$로 들어오는 유량
아래 그래프에서 $f$는 나가는 유량(3)만 있으므로 3이 됩니다.
위 그래프에 edge cut을 수행해 두 개 부분그래프로 쪼개 보겠습니다. $s$가 속한 부분그래프를 $S$, $t$가 속한 부분그래프를 $T$라고 둡니다. 이 때 $S$와 $T$ 사이의 순 유량(net flow) $f$와 용량 $C$는 각각 다음과 같이 정의됩니다.
\[\begin{align*} f\left( S,T \right) &=\sum _{ u\in S }^{ }{ \sum _{ v\in T }^{ }{ f\left( u,v \right) } } -\sum _{ u\in S }^{ }{ \sum _{ v\in T }^{ }{ f(v,u) } } \\ c\left( S,T \right) &=\sum _{ u\in S }^{ }{ \sum _{ v\in T }^{ }{ c\left( u,v \right) } } \end{align*}\]예를 들어보겠습니다. 아래 그래프를 빨간색 선을 따라 edge cut을 수행했다고 칩시다. $f(S,T)$는 $S$에서 $T$로 가는 유량을 $T$에서 $S$로 가는 유량을 빼서 구하므로 4-1=3이 됩니다. $c(S,T)$는 $S$에서 $T$로 가는 용량만을 따지므로 2+3=5가 됩니다.
이번엔 파란색 선을 따라 edge cut을 수행했다고 칩시다. $f(S,T)=4-1=3$입니다. $c(S,T)=3+3=6$입니다.
정리 및 증명
edge cut으로 최대 유량을 구하는 데 있어 두 가지 중요한 정리가 있습니다. 첫번째는 어떻게 cut을 하더라도 유량값($f$)은 동일하다라는 사실입니다. (fot any cut ($S,T$), $f(S,T)=$|$f$|) 위 그림 예제로 설명해 보자면 빨간색 선을 따라 cut을 하든, 파란색 선을 따라 cut을 하든 $f$는 3으로 같습니다. 이는 다른 선을 따라 cut을 해도 마찬가지입니다.증명은 다음과 같습니다.
두번째 중요한 정리는 $S$와 $T$를 어떻게 자르든 $S,T$ 사이의 유량은 용량보다 작다는 것입니다. (The value of any flow)≤capacity of any cut)
algorithm
이같은 사실을 활용해 우리는 모든 가능한 경우에 대해 edge cut을 수행한 뒤 그 가운데 가장 작은 용량(capacity)을 선택하면 그것이 전체 그래프의 최대 유량이 됨을 알 수 있습니다. 위 그림 예제로 설명해보자면, 빨간색 선으로 잘라보고, 파란색 선으로 잘라보고, 다른 모든 가능한 경우의 수에 대해 잘라봐서 $c(S,T)$ 값을 각각 구하고, 이 가운데 가장 적은 값을 최대 유량으로 반환하는 겁니다. 한편 만일 최소 비용으로 그래프의 최대 유량을 높이고 싶다면 가장 적은 $c(S,T)$에 대응하는 엣지들의 용량을 높여주면 됩니다.
Comments