[용어]
Source: 시작점
Sink: 도착점
Capacity: 용량 (간선에서 소화 가능한 최대 양 or 값)
Flow: 유량 (간선에서 용량을 점유하고 있는, 사용하고있는 양 or 값)
c(a, b): 정점 a 에서 b로, 소화 가능한(남은) 용량 값
f(a, b): 정점 a 에서 b로, 사용하고 있는(쓴) 유량 값
[NetWorkFlow]
다음과 같은 NetWorkFlow그래프가 있을때 각 edge마다 적혀있는 숫자는 노드에서 노드까지 보낼 수 있는 최대 capacity(용량)이다. 즉 NetWorkFlow란 그래프를 Capacity관점으로 바라보는 것이다. network flow의 특징을 정리하면 다음과 같다.
1. 용량의 제한(capacity constraint): 유량은 그 간선의 용량을 초과할 수 없다.
노드 0에서 노드 1까지의 Capacity가 16일때 16을 넘어서는 데이터 패킷을 전송 할 수 없다.
2. 유량의 보존(conservation of flows) : 소스와 싱크를 제외한 정점에는 들어오는 유량과 나가는 유량은 같다.
vertex 0에서 vertex1, vertex3 거쳐 vertex 5까지 데이터를 12보낼때, 모든 경로에 12가 보내진다. 즉 중간에 소모되거나 새는 데이터는 존재하지 않고 전부 보존된다. 이때 각 edge별로 residual capacity(잔여용량)은 순서대로 4,0,8이 된다.
3. 유량의 대칭성(skew symmetry) : u→v로 f만큼의 유량이 흐르면 v→u로 -f만큼 유량이 흐른다고 생각한다. f(a, b)=-f(b,a)가 성립한다.
예를들어 vertex1에서 vertex2까지 데이터 패킷4를 전송한다고 하면 vertex2에서 1로 보낼수있는 residual capacity는 8이 되게 된다. 기존의 4와 vertex1에서 2로 보내게 되어 생기는 여유분4가 되는것이다. 이렇게 생각하면 이해하기 쉽다. 기존에 받았던 데이터 패킷을 반환할 수 있다.(반환하기 위한capacity를 부여)
[Ford-fulkerson]
포드 풀커슨의 경우 Network flow의 특징을 이용해서 Source에서 부터 sink또는 target까지 최대 보낼 수 있는 maximum flow를 찾는것이다.
알고리즘은 다음과 같다.
BFS또는 DFS 탐색을 통해서 source부터 남은 Path의 residual capacity가 0보다 큰 path들을 바탕으로 sink에 도달하면 되고,
더이상 흐를 수 없을때까지 전송하면 된다.
시뮬레이션을 하면 다음과 같다.
1.(0->1->3->5) 12 packet을 보낼때
2.(검은색:남은 Capacity,빨간색: 흐르고 있는 유량 및, 유량의 대칭성으로 인해서 생긴 반대 남은 유량)
3[최종]
다음과 같이 시뮬레 이션하면 최대 흐르는 유량은 23인것을 알 수 있다. 이때
source vertex인 0에서 나가고 있는 패킷수와 sink에서 들어오는 패킷수가 동일 한것을 알수 있으며 이를 통해 유량의 보존(conservation of flows)를 확인 할 수있다.
