12.3.3 서로소 경로

서로소 경로

많은 그래프 문제를 최대 유량 문제로 변환하여 풀 수 있다. 그러한 문제의 첫 번째 예제는 다음과 같다. 소스와 싱크가 있는 방향 그래프에 대해, 소스에서 싱크로 가는 서로소 경로(disjoint path) 의 최대 개수를 찾으려 한다.

간선 서로소 경로

먼저 소스에서 싱크로 가는 간선 서로소 경로(edge-disjoint path) 의 최대 개수를 찾는 문제를 생각해 보자. 이는 각 간선이 최대 하나의 경로에만 포함될 수 있다는 뜻이다. 예를 들어 그림 24에서 간선 서로소 경로의 최대 개수는 $2$가 된다($1\to 2\to 4\to 3\to 6$과 $1\to 4\to 5\to 6$).

• 그림 24. 1번 노드에서 6번 노드로 가는 간선 서로소 경로
  • 

간선 서로소 경로의 최대 개수는 각 간선의 용량이 $1$인 그래프의 최대 유량과 같다. 최대 유량을 구한 뒤에는 소스에서 싱크로 가는 경로를 탐욕법 기반으로 찾으면 된다.

노드 서로소 경로

다음으로 소스에서 싱크로 가는 노드 서로소 경로(node-disjoint path) 의 최대 개수를 찾는 문제를 생각해 보자. 이 경우, 소스와 싱크를 제외한 모든 노드는 최대 하나의 경로에만 포함될 수 있으며, 따라서 간선 서로소 경로보다 개수가 작을 수 있다. 예제 그래프에서 노드 서로소 경로의 최대 개수는 $1$이다(그림 25).

• 그림 25. 1번 노드에서 6번 노드로 가는 노드 서로소 경로
  • 

이 문제 역시 최대 유량 문제로 변환할 수 있다. 각각의 노드가 최대 하나의 경로에만 포함될 수 있기 때문에 노드를 지나는 유량을 제한할 필요가 있다. 이를 위해 각각의 노드를 두 개의 노드로 나누는데, 첫 번째 노드에는 들어오는 간선(in)을 연결하고, 두 번째 노드에는 나가는 간선(out)을 연결하며, 첫 번째 노드에서 두 번째 노드로 가는 간선(in-path)을 추가한다. 그림 26에 이 방식으로 만든 그래프와 최대 유량이 나와 있다.

• 그림 26. 노드를 지나는 유량을 제한하는 그래프 만들기
  •