Flow Network - 유량 네트워크

참고자료

wikipedia https://en.wikipedia.org/wiki/Flow_network

Flow network - Wikipedia

유량 네트워크가 성립하기 위한 3가지 조건

1	Capacity Constraint (수용량 제한)	f(u,v) <= c(u,v)
2	Skew Symmetry (편향 대칭성)	f(u,v) = -f(v,u)
3	Flow Conservation (유량 보존)	u가 s 혹은 t가 아닐때 u의 진입, 진출 간선의 합 = 0

유량 네트워크는 정점간의 이동을 구할때 용이합니다!

 

말 그대로 흐름이 있는 그래프인데요.

 

다른 그래프들의 간선이 cost이라는 가중치를 갖는 반면 유량 네트워크의 간선은 capacity와 flow를 갖습니다.

 

cost는 응용에 따라 거리가 될 수도 있고, 금액이 될 수도 있습니다!

 

간선이 길이라면 flow는 몇명의 사람들이 그 길을 이용했는지를 표현할 수 있고요.

 

간선이 배수관이라면 flow는 얼마만큼의 물이 그 배수관을 타고 흐르는지 표현 할 수 있습니다!

 

capacity는 이 flow의 최대값을 나타내는데요.

 

배수관은 휴지두루마리 만한데 100톤의 물을 휴지두루마리 만한 배수관에 밀어넣는다면???

 

안됩니다... 안되요... !

 

각 간선은 capacity >= flow의 조건을 만족시킵니다.

 

물이 하수구로 빠지는 예를 들면

각각의 간선 가중치는 하수구 배관이 통과시킬 수 있는 물의 수용량이라고 하겠습니다~

 

이때 s에서 t로 물이 1만큼 흘러가면

이런 모양이 되는데요. 

 

s는 source(발신지)를 의미하고, t는 sink(끝)을 의미합니다.

 

만든 사람이 정한거 같으니까 외우도록 합시다 ㅜ_ㅜ..

 

아직 물이 더 흐를 수 있네요. 1을 더 흘려보면

 

이렇게 됩니다. 물을 2만큼 보냈고 2만큼 잘 도착했습니다.

 

이것을 수식으로 표현하면

function f(u,v) - 정점 u에서 정점 v로 흐른 양

f(s,1) = 1, f(s,2) = 1, f(1,t) = 1, f(1,3) = 1, f(3,t) =1 가 됩니다.

 

그런데 지금 그래프에서는 물이 중간에 복사된 것 처럼 각각의 정점을 지날때마다 증가하고 있습니다.

 

network flow에서는 유량을 표현하기 위해 아래의 방정식을 만족합니다.

f(u,v) = -f(u,v)

 

그러니까 물길은 한순간에 하나씩만 존재해야합니다.

 

1이 흐른만큼 반대방향으로 1을 표시해서 물이 흐른 뒤에 계속 물이 어딘가에서 만들어지는 현상을 없앨 수 있어요.

 

또 그래프를 잘 보면 각 정점으로 들어오는 간선의 양과 각 정점에서 나가는 간선의 가중치 양이 같다는 것을 알 수 있습니다.

 

정점 u와 연결된 간선은

f1 + f2 = f3 + f4 + f5

f1 + f2 - f3 - f4 - f5 = 0의 관계를 만족시킵니다.

 

다음 포스팅은 유량 네트워크를 구현하는 알고리즘인 ford-fulkerson에 대해서 알아볼게요!