Network Flow

그래프 두 노드 사이에 얼마나 많은 유량을 보낼 수 있는지 계산하는 알고리즘 network flow, maximum flow 라고 불린다

출발점에서 목적지까지 물을 흘려보낼때, 가장 많은 양의 물을 흘려보내는 방법 찾기 알고리즘이다. 최소 경로 문제는 그동안 많이 접할 수 있어서 익숙할 수 있지만, 여기에 용량이라는 개념이 추가된다. \(\text{capacity >= flow}\)로 최대 용량 만큼 흘려보낼 수 있다. 다른 것들은 비슷하다. 다르게 표현하면 \(c(u,v) >= f(u,v)\)이다.

wordpool

Node : 정점 하나의 지점

Capacity : 용량 c 노드 u에서 v로 가는 간선의 용량(가중치) \(c(u,v)\)

Flow : 유량 f 정점 u에서 v로의 간선에 실제로 흐르는 유량 \(f(u,v)\)

Residual capacity : 잔여 용량 r 간선의 용량과 유량의 차이, 간선에 추가적으로 흘려 보낼 수 있는 유량 \(r(u,v) = c(u,v) - f(u,v)\)

Source \(s\), Sink \(t\) 유량이 시작되는 지점, 유량이 도착하는 지점 유량은 소스에서부터 싱크로 흐르게 되는 구조

Ford-Fulkerson

최소컷

(1)\[ \tag{유량의 대칭성} f(u,v) = -f(v,u) \]

간선 (u,v) 방향으로 flow가 존재한다면(f(u,v)>0), 역방향으로는 음의 유량이 그만큼 흐르고 있는 것으로 취급한다는 의미를 유량의 대칭성이라고 말한다. 간선 (u,v)가 존재한다면 c(u,v)가 양수고, c(v,u)는 0으로 취급된다. 따라서 그래프에서는 없는 간선이지만 가상으로는 있는 역방향 간선에 대한 성질로 접근하는 것이 해당 알고리즘의 포인트다. 역방향 간선으로 흘려보낸다는 의미는 곧 다른 간선으로 대신 흘려보낸다는 의미와 동등하다.

폴트포커슨에서 중요한 것은 위의 유량의_대칭성을 사용한다는 것이다. 원래는 없는 간선일지라도 해당 성질을 이용하면 숨어있는 간선의 잔여유량을 찾을 수 있다.

1. s \(\to\) t로 가는 경로 아무거나 하나 찾는다. 이때 경로는 단순 경로이고, 경로상의 모든 간선에 아직 여유 용량이 남아있다. 즉 \(c(u,v)-f(u,v) > 0\)

2. 차단 간선을 찾는다. 이 간선은 경로상에서 \(c(u,v)-f(u,v)\)의 값이 최소인 간선이다. 많아봐야 이만큼의 유량을 더 보낼 수 있다. 이는 잔여용량 \(r\) 이다. 잔여용량이 0이면 더이상 해당 간선에는 유량을 보낼 수 없다.

3. 경로상 모든 간선에 \(r\)만큼의 유량을 추가한다. 따라서 경로상 모든 간선에 대해서 \(f(u,v)+=r\)이 되고, 위의 대칭성을 이용해서 \(f(v,u)-=F\)도 해줘야한다.

위의 3 단계를 더이상 증가 경로가 없을 때 까지 반복한다. 증가 경로를 찾고, 찾은 경로에 대해 가능한 한 많은 유량을 흘려보내는 것의 반복이다.

보통 BFS 너비우선탐색으로 많이 푼다.

minimum cut

그래프에서 두 개의 정점 집합을 구분하는 가장 짧은 경로를 찾는 문제

기본적으로 Cut이라는 것은 그래프의 정점을 2개의 서로 다른 집합으로 나누는 것을 말한다. 여기서 가중치(비용)이 없는 그래프의 경우는 자른 간선의 개수가 cut의 비용이고, 있는 그래프는 자른 간선의 가중치의 합이 cut의 비용이다.

그렇기에 min cut 문제는 집합을 구분하기 위해 그은 간선의 가중치 합이 가장 적게하기 문제라고 볼 수 있다. 최소 컷 문제는 플로우와 관련이 매우 많다. 정점 두 개를 분리시키는 최소 컷의 비용은 각 간선의 비용을 용량이라 할때 최대 유량과 동치이다.

다시 한 번 정리하자면, 최대 유량으로 흘려보내는 상황에서는 어떤 컷을 선택하더라도 컷에 포함된 간선들에서 흐르는 물의 양은 동일하다는 것이다.

referance

• 라이 - 최소 컷

• EVErNew - Network Flow(최대유량,최소 컷) 알고리즘