네트워크 플로우

 

 

네트워크 플로우 알고리즘은 직관적이지도 않고 증명도 어렵고 플로우를 사용하는 문제인 걸 알아도 "이게 플로우라고?"라는 생각이 드는 알고리즘입니다. 최대한 직관적으로 이해할 수 있도록 해 보겠습니다.

그래서 뭐하는 알고리즘인가?

다음과 같은 문제를 생각해 보겠습니다.

그래프가 하나 주어집니다. 주어진 그래프에는 $N$개의 정점과 $M$개의 파이프가 있습니다. 각 파이프는 물을 한쪽 방향으로만 흘릴 수 있습니다. 각 파이프의 흐를 수 있는 양은 다릅니다. 시작 정점과 끝 정점이 주어졌을 때, 시작 정점에서 끝 정점으로 최대한 많은 양의 물을 보내고자 합니다. 얼마나 보낼 수 있습니까?

 

예를 들어 다음 그래프 같은 경우(s부터 e까지)

 

다음과 같이 물을 흘리면 15만큼 흘릴 수 있습니다.

 

시간복잡도 같은 것들을 무시하고 생각해 봅시다. 이런 방식은 어떨까요?

1. bfs든 dfs든 아무 경로 하나를 찾습니다.
2. 선택된 경로로 최대한 많은 양을 흘립니다.
3. 경로를 찾지 못할 때 까지 진행합니다.

이렇게 하면 해결할 수 있을까요? 다음 경우를 생각해 봅시다.

 

 

1에서 4까지 흘릴 수 있는 물의 양을 구할 것입니다. 계산을 편하게 하기 위해 흘릴 수 있는 물의 양은 전부 1이라고 합시다.

처음에 1 -> 2 -> 3 -> 4 경로를 찾으면 더 이상 다른 길을 찾을 수 없습니다.

하시잠 실제로는 2만큼의 물을 흘릴 수 있습니다.

 

 

저희는 첫번째 길로 1 -> 2 -> 3 -> 4를 찾은 경우에도 이 문제를 해결해야 합니다. 만약 이 전에 선택한 길을 되돌릴 수 있다면 이 문제 풀 수 있지 않을까요? 이것을 "역방향 간선"으로 해결합니다.

 

길 1 -> 2 -> 3 -> 4 를 찾았을 때 그 길을 없애고 반대 방향으로 길을 만들어 줍니다. 가중치가 있는 그래프의 경우에는 길의 가중치를 흘릴 수 있는 물의 양만큼 줄이고 그 양만큼 반대 방향으로 흐르는 간선을 추가해 줍니다. 그 상태에서 새로운 길을 찾습니다. 예시의 경우 반대 방향으로 간선을 만들어 주면

 

다음과 같이 되고 그 상태로 길을 찾으면

 

이런 파란색 경로를 찾게 됩니다. 이 경로에 대해서도 역방향 간선을 만들어 주면

이렇게 됩니다. 2 -> 3에 해당하는 경로는 다시 정방향으로 돌아옵니다.

 

역방향 간선에 대해서 조금 더 생각해 봅시다. 처음 1 -> 2 -> 3 -> 4 길을 찾은 다음 두번째 경로로 1 -> 3 까지 진행한 상황입니다. 빨간색이 첫번째 길, 파란색이 두번째 길입니다.

 

이 때, 빨간색의 일부와 파란색을 바꾸어도 진행을 달라지지 않습니다.

즉,

1. 처음에 1 -> 2 -> 3 -> 4 길을 찾고
2. 두번째 길로 1 -> 3 까지 갔다가
3. 역방향 간선 3 -> 2를 거쳐 2 -> 4로 도달한 것

과

1. 처음부터 1 -> 3 ->4 길을 찾고
2. 두번째 길로 1 -> 2 -> 3 까지 갔다가
3. 더이상 길이 없으니 3 -> 2로 돌아와 2 -> 4로 도달한 것

이 같은 동작이라는 것입니다.

이런 식으로 계속 진행하면 최대한 많은 물을 흘릴 수 있습니다.

 

이 방식 대로라면 더 많은 물을 흘릴 수 있다는 것 까진 알겠지만 이게 정말 최대인지는 증명이 되지 않았습니다. 이 증명은 minimum cut maximum flow에 대해 이야기를 해야 합니다(https://codestudycafe.tistory.com/36)