6-9. 그래프: 네트워크 플로우

1. 네트워크 플로우 (Network Flow) 개요

네트워크 플로우는 그래프 이론의 한 분야로, 흐름 네트워크(Flow Network)라고 불리는 특별한 종류의 유향 그래프에서 최대 흐름(Maximum Flow)을 계산하는 문제를 다룹니다. 이는 다양한 실생활 문제들을 모델링하고 해결하는 데 유용합니다. 예를 들어, 파이프라인을 통한 액체의 최대 흐름, 통신 네트워크를 통한 데이터 전송량, 또는 교통 네트워크에서 가능한 최대 차량 흐름 등을 분석하는 데 사용될 수 있습니다.

1) 흐름 네트워크 (Flow Network)

흐름 네트워크는 다음과 같은 특징을 가집니다.

• 유향 그래프(Directed Graph): 각 간선은 흐름의 방향을 나타냅니다.
• 용량(Capacity): 각 간선은 흐름의 최대 용량을 나타내는 음이 아닌 값을 가집니다. 이는 간선을 통해 흐를 수 있는 최대 흐름의 양을 의미합니다.
• 소스(Source) 노드: 흐름이 시작되는 노드, 보통 s로 표시합니다.
• 싱크(Sink) 노드: 흐름이 끝나는 노드, 보통 t로 표시합니다.

2) 흐름 (Flow)

흐름은 네트워크의 각 간선을 통해 흐르는 값으로, 다음과 같은 제약 조건을 만족해야 합니다.

• 용량 제약(Capacity Constraint): 간선의 흐름은 해당 간선의 용량을 초과할 수 없습니다. 즉, $f(u, v) \le c(u, v)$ 입니다. 여기서 $f(u, v)$는 간선 $(u, v)$의 흐름, $c(u, v)$는 간선 $(u, v)$의 용량을 나타냅니다.
• 반대칭성(Skew Symmetry): 두 노드 사이의 흐름은 반대 방향으로 흐르는 흐름의 음수와 같습니다. 즉, $f(u, v) = -f(v, u)$ 입니다.
• 유량 보존(Flow Conservation): 소스와 싱크를 제외한 모든 노드에서 들어오는 흐름과 나가는 흐름의 합은 같습니다. 즉, $\sum_{u} f(u, v) = 0$ 입니다.

3) 최대 유량 문제 (Maximum Flow Problem)

최대 유량 문제는 주어진 흐름 네트워크에서 소스에서 싱크로 보낼 수 있는 최대 흐름의 양을 찾는 문제입니다. 이 문제는 다양한 최적화 문제의 핵심으로 사용되며, 효율적인 알고리즘을 통해 해결할 수 있습니다.

2. Ford-Fulkerson 알고리즘

Ford-Fulkerson 알고리즘은 최대 유량 문제를 해결하기 위한 기본적인 알고리즘입니다. 이 알고리즘은 잔여 네트워크(Residual Network)를 사용하여, 흐름을 개선하는 경로를 반복적으로 찾습니다.

1) 잔여 네트워크 (Residual Network)

잔여 네트워크는 주어진 흐름 네트워크에서 각 간선의 남은 용량을 나타내는 그래프입니다. 즉, 간선 $(u, v)$에 흐름 $f(u, v)$가 흐르고 있다면, 잔여 네트워크에는 용량이 $c(u, v) - f(u, v)$인 간선 $(u, v)$와 용량이 $f(u, v)$인 간선 $(v, u)$가 존재합니다. 역방향 간선 $(v, u)$는 흐름을 "취소"하는 역할을 하여, 흐름을 재분배할 수 있게 해줍니다.

2) 증강 경로 (Augmenting Path)

증강 경로는 잔여 네트워크에서 소스에서 싱크로 가는 경로입니다. 이 경로는 흐름을 증가시킬 수 있는 경로를 나타냅니다. 증강 경로를 찾은 후, 해당 경로 상의 모든 간선에 흐름을 추가하여 전체 흐름을 증가시킬 수 있습니다. 추가할 흐름의 양은 증강 경로 상의 간선 중 최소 잔여 용량과 같습니다.

3) Ford-Fulkerson 알고리즘의 동작 방식

1. 초기화: 모든 간선의 흐름을 0으로 설정합니다.
2. 반복: 잔여 네트워크를 구성하고, 잔여 네트워크에서 증강 경로를 찾습니다.
3. 증강 경로가 존재하면, 해당 경로 상의 최소 잔여 용량을 찾아 흐름을 증가시킵니다.
4. 증강 경로가 없으면 알고리즘을 종료합니다. 현재 흐름이 최대 유량입니다.

4) Ford-Fulkerson 알고리즘의 의사 코드

Algorithm Ford-Fulkerson(G, s, t)
    // G는 그래프, s는 소스, t는 싱크
    initialize flow f to 0
    while there exists an augmenting path p in Gf
        do augment flow f along path p
    return f

5) Ford-Fulkerson 알고리즘의 문제점

Ford-Fulkerson 알고리즘은 이론적으로는 간단하지만, 증강 경로를 찾는 방식에 따라 성능이 크게 달라질 수 있습니다. 최악의 경우, 탐욕적인 선택으로 인해 실행 시간이 $O(E \cdot |f^*|)$가 될 수 있습니다. 여기서 $E$는 간선의 수, $|f^*|$는 최대 유량의 값입니다. 만약 용량이 정수가 아닌 경우, 알고리즘이 무한히 반복될 수도 있습니다.

3. Edmonds-Karp 알고리즘

Edmonds-Karp 알고리즘은 Ford-Fulkerson 알고리즘의 개선된 버전으로, 증강 경로를 찾는 방식을 너비 우선 탐색(Breadth-First Search, BFS)을 사용하여 구현합니다. 이는 증강 경로를 찾는 순서를 보장하여, 최악의 경우에도 $O(V \cdot E^2)$의 시간 복잡도를 가지도록 합니다. 여기서 $V$는 노드의 수입니다.

1) Edmonds-Karp 알고리즘의 핵심 아이디어

Edmonds-Karp 알고리즘은 잔여 네트워크에서 증강 경로를 찾을 때, BFS를 사용하여 최단 경로를 찾습니다. 최단 경로를 찾음으로써, 각 반복마다 흐름이 증가하는 정도를 최대화하고, 알고리즘의 효율성을 높입니다.

2) Edmonds-Karp 알고리즘의 동작 방식

1. 초기화: 모든 간선의 흐름을 0으로 설정합니다.
2. 반복: 잔여 네트워크를 구성하고, BFS를 사용하여 증강 경로를 찾습니다.
3. 증강 경로가 존재하면, 해당 경로 상의 최소 잔여 용량을 찾아 흐름을 증가시킵니다.
4. 증강 경로가 없으면 알고리즘을 종료합니다. 현재 흐름이 최대 유량입니다.

3) Edmonds-Karp 알고리즘의 의사 코드

Algorithm Edmonds-Karp(G, s, t)
    // G는 그래프, s는 소스, t는 싱크
    initialize flow f to 0
    while there exists an augmenting path p in Gf (using BFS)
        do augment flow f along path p
    return f

Edmonds-Karp 알고리즘은 Ford-Fulkerson 알고리즘보다 효율적이며, 일반적으로 실용적인 문제에 더 많이 사용됩니다.

4. 응용 문제

네트워크 플로우는 다양한 분야에서 응용될 수 있습니다. 다음은 몇 가지 예시입니다.

1) 이분 매칭 (Bipartite Matching)

이분 매칭은 두 그룹의 노드 간의 매칭 문제를 다룹니다. 예를 들어, 남녀 매칭 문제에서 각 남자가 여자들과의 관계를 가질 수 있고, 이 관계의 유무를 찾는 문제입니다. 이 문제는 네트워크 플로우를 사용하여 효율적으로 해결할 수 있습니다.

• 소스에서 한 그룹의 노드(예: 남자)로 간선을 연결하고, 다른 그룹의 노드(예: 여자)에서 싱크로 간선을 연결합니다.
• 두 그룹 사이의 가능한 매칭 관계를 나타내는 간선을 추가합니다. 각 간선의 용량은 1로 설정합니다.
• 최대 유량을 계산합니다. 최대 유량의 값은 가능한 최대 매칭의 크기를 나타냅니다.

2) 이미지 분할 (Image Segmentation)

이미지 분할은 이미지를 여러 영역으로 나누는 문제입니다. 네트워크 플로우는 이러한 문제를 해결하는 데 사용될 수 있습니다.

• 각 픽셀을 노드로 표현하고, 인접한 픽셀 간에 간선을 연결합니다.
• 각 픽셀의 속성(예: 색상)에 따라 간선의 용량을 설정합니다.
• 특정 영역을 소스로, 다른 영역을 싱크로 설정합니다.
• 최대 유량을 계산하여 이미지의 영역을 분할합니다.

3) 프로젝트 스케줄링 (Project Scheduling)

프로젝트 스케줄링은 여러 작업을 수행하는 데 필요한 최소 시간을 결정하는 문제입니다. 네트워크 플로우를 사용하여 각 작업 간의 종속성을 모델링하고, 프로젝트의 최소 완료 시간을 계산할 수 있습니다.

4) 기타 응용

• 데이터 전송: 네트워크 내에서 데이터 패킷의 최대 전송량을 계산하는 데 사용됩니다.
• 교통 흐름 모델링: 도시의 교통 네트워크에서 가능한 최대 차량 흐름을 계산하는 데 사용됩니다.
• 자원 할당: 제한된 자원을 여러 작업에 할당하는 문제에 적용됩니다.

5. 구현 시 주의사항

네트워크 플로우 알고리즘을 구현할 때는 다음과 같은 사항에 주의해야 합니다.

1) 간선 방향

그래프가 유향 그래프인지, 무향 그래프인지에 따라 간선의 방향을 올바르게 설정해야 합니다. 네트워크 플로우는 유향 그래프에서 정의되므로, 무향 그래프의 경우 양방향 간선을 추가하여 유향 그래프로 변환해야 합니다.

2) 용량 제한

간선의 용량을 올바르게 설정해야 합니다. 용량은 간선을 통해 흐를 수 있는 최대 흐름의 양을 나타내므로, 문제의 특성에 맞게 설정해야 합니다.

3) 잔여 네트워크 관리

잔여 네트워크를 효율적으로 관리해야 합니다. Ford-Fulkerson 알고리즘과 Edmonds-Karp 알고리즘 모두 잔여 네트워크를 사용하므로, 잔여 용량을 정확하게 계산하고 업데이트해야 합니다.

4) 오버플로우

흐름 값을 저장할 때 오버플로우가 발생하지 않도록 주의해야 합니다. 최대 유량은 간선의 용량보다 작거나 같으므로, 적절한 자료형을 사용해야 합니다.

6. 결론

네트워크 플로우는 다양한 실생활 문제를 모델링하고 해결하는 데 유용한 강력한 도구입니다. Ford-Fulkerson 알고리즘과 Edmonds-Karp 알고리즘은 최대 유량 문제를 해결하기 위한 기본적인 알고리즘이며, 이들을 이해하는 것은 그래프 이론과 알고리즘을 학습하는 데 중요한 과정입니다. 이 개념들을 이해하고 적절하게 활용한다면, 복잡한 문제들을 효율적으로 해결할 수 있을 것입니다.