최대 유량 문제는 시작점 s에서 도착점 t로 흘려보낼 수 있는 양을 늘리는 문제입니다. 각 간선의 용량을 넘지 않고, 중간 정점에서는 들어온 양과 나간 양이 같아야 합니다. 단순히 처음 발견한 경로에 가능한 만큼 흘리는 것만으로는 충분하지 않습니다. 나중에 그 선택을 일부 취소하고 다른 경로로 재배치할 수 있어야 하므로, 현재 flow를 표현하는 잔여 그래프(residual network)에 순방향 여유와 역방향 취소 여유를 함께 둡니다.
유량의 보존과 값
유향 그래프의 간선 (u,v)에 용량 c(u,v)와 유량 f(u,v)를 둡니다. 허용 조건은 0 ≤ f(u,v) ≤ c(u,v)이고, s와 t가 아닌 정점 v에서는 Σf(u,v)=Σf(v,w)입니다. 유량의 값 |f|는 s에서 나가는 총량이며, 보존 때문에 t로 들어오는 총량과 같습니다.
알고리즘이 저장하는 표현은 다양합니다. 원래 간선별 flow를 저장하고 잔여량을 계산할 수도 있고, forward/reverse edge 객체에 현재 잔여 용량을 직접 저장할 수도 있습니다. 후자의 경우 역간선은 입력 도로가 아니라 “앞으로 원래 flow를 줄일 수 있는 선택”입니다. 출력할 때는 원래 간선 ID와 방향으로 필터링해 실제 flow를 복원해야 합니다.
정수 capacity와 flow 0에서 시작하면 잔여 용량도 정수입니다. 증가 경로의 bottleneck은 그 경로의 잔여 용량 최솟값이므로 정수이고, 한 번의 갱신 뒤에도 모든 flow가 정수로 남습니다. 이 적분성은 Ford–Fulkerson의 정수 입력에서 자연스럽게 얻지만, 실수 capacity를 넣고 동일한 종료·비교 정책을 그대로 주장하는 근거는 아닙니다.
잔여 네트워크와 역간선
현재 원래 간선 (u,v)의 flow가 f라면 순방향 잔여 용량은 c-f, 역방향 잔여 용량은 f입니다. 전자는 더 보낼 수 있는 양이고 후자는 이미 보낸 양 중 되돌릴 수 있는 양입니다. 어떤 간선이 두 방향으로 실제 입력에 동시에 존재한다면 “원래 반대 간선”과 “flow 취소용 역간선”을 edge identity로 구분해야 합니다. 단순히 두 정점을 키로 덮어쓰면 용량이 합쳐지거나 역갱신 대상이 섞일 수 있습니다.
그림을 글로 읽기
- 원래 간선 u→v: capacity = 5 · 현재 flow = 3
- 순방향 잔여: 5-3 = 2 · 더 보낼 수 있음
- 역방향 잔여: 3 · 보낸 양을 취소
- 다음 증가 경로: 두 방향 선택을 포함 · 기존 경로 재배치
- 원래 간선 u→v → 순방향 잔여: c-f
- 원래 간선 u→v → 역방향 잔여: f
- 순방향 잔여 → 다음 증가 경로: 전진
- 역방향 잔여 → 다음 증가 경로: 취소 후 우회
증가량 Δ를 잔여 경로에 더할 때 경로의 forward edge에는 잔여 용량을 Δ만큼 줄이고, reverse edge에는 Δ만큼 늘립니다. 같은 원래 edge 쌍을 객체 포인터로 연결했다면 e.cap -= Δ, e.rev.cap += Δ와 같은 갱신이 됩니다. 역간선을 따라간 경우에는 원래 flow가 줄어드는 효과가 나며, 마지막 flow를 원래 간선 기준으로 읽을 때만 이 표현을 다시 해석합니다.
잘못된 첫 경로의 수정
역간선의 필요성을 실제로 보이려면 첫 경로가 공유 용량을 잘못 점유하는 입력을 택해야 합니다. 다음 다섯 원래 간선의 용량을 모두 1로 두겠습니다: s→u, s→v, u→v, u→t, v→t. 처음에 경로 선택 순서를 강제해 s-u-v-t로 1을 보냈다고 합시다. 그러면 원래 간선의 flow는 s→u=1, u→v=1, v→t=1이고, s→v와 u→t는 아직 1의 여유가 있습니다.
이 상태에서 두 번째 단위를 원래 간선만으로 보내려면 s→v 뒤에 v→t가 필요하지만 v→t는 이미 포화되어 있습니다. 잔여 그래프에는 v→u라는 역잔여 간선이 생겨 있고 그 용량은 현재 u→v flow인 1입니다. 따라서 s-v→u(여기서 v→u는 u→v의 reverse) →t라는 잔여 경로가 존재합니다. 이 경로에 1을 augment하면 s→v와 u→t의 flow는 1이 되고, 역간선을 따라간 u→v의 flow는 1에서 0으로 줄어듭니다. 최종 원래 간선 flow는 s→u=1, s→v=1, u→t=1, v→t=1, u→v=0이며 값은 2입니다.
즉 두 번째 증가가 끝난 뒤에는 첫 경로의 중간 간선 u→v가 취소되어 두 개의 직접 경로 s-u-t, s-v-t로 재배치됩니다. 역간선을 출력 경로로 내보내는 것이 아니라, 현재 선택을 되돌리는 계산 장치로만 사용했다는 점이 핵심입니다. 역간선을 빼면 첫 선택이 고정되어 값 1에서 멈추지만 실제 최대값 2를 놓칩니다.
증가 경로와 종료 조건
잔여 그래프에서 s에서 t로 가는 양의 잔여 용량 경로를 찾고, 경로 bottleneck만큼 augment합니다. BFS를 쓰는 Edmonds–Karp라면 큐에서 s를 시작하고 양의 잔여량이면서 아직 방문하지 않은 정점만 넣습니다. t에 도착하면 parent edge를 거꾸로 따라 bottleneck을 계산하고, 같은 edge 객체 쌍을 갱신합니다.
반대로 잔여 그래프에서 t에 도달할 수 없으면 더 이상 증가 경로가 없습니다. 이 상태는 현재 알고리즘이 임의의 경로를 놓친 것이 아니라, 현재 flow에서 합법적인 추가·취소·우회의 조합이 모두 막혔다는 의미입니다. 최대 유량 정리는 이 상태를 최소 컷과 연결합니다. 다만 구현에서 cap == 0 판정을 부동소수점 오차로 잘못 처리하거나, 역간선을 BFS에서 제외하면 “경로 없음”의 의미가 달라집니다.
최소 컷과 도달 가능 집합
종료한 잔여 그래프에서 s로부터 양의 잔여 용량을 따라 도달 가능한 정점 집합을 S, 나머지를 T라고 하겠습니다. s는 S에 있고 t는 증가 경로가 없으므로 T에 있습니다. 원래 그래프에서 S→T인 간선이 아직 포화되지 않았다면 그 간선의 남은 용량을 따라 T로 더 갈 수 있었으므로 모순입니다. 따라서 이 방향의 모든 간선은 포화됩니다.
이제 flow 값과 cut capacity가 같음을 봅니다. S에서 T로 향하는 원래 간선은 모두 capacity만큼 flow가 흐르고, T에서 S로 향하는 원래 간선은 잔여 역간선이 남아 있지 않다는 도달성 조건 때문에 실제 flow가 0이어야 합니다. 그 결과 컷을 가로지르는 순유량은 S→T capacity 합과 같고, 어떤 flow도 어느 cut capacity보다 클 수 없으므로 이 flow와 cut은 동시에 최적입니다.
S를 만들 때는 잔여 그래프의 reverse edge도 따라갈 수 있습니다. 하지만 cut capacity를 계산할 때 reverse residual을 원래 간선 capacity로 더하면 안 됩니다. 도달성은 현재 flow를 수정할 수 있는 방향을 찾는 절차이고, cut capacity는 원래 네트워크에서 S→T로 향하는 간선들의 capacity 합이라는 서로 다른 계산입니다.
Edmonds–Karp의 경로 선택 비용
Ford–Fulkerson은 증가 경로를 어떤 방식으로 선택하느냐에 따라 실행 횟수가 capacity 값이나 선택 순서의 영향을 받습니다. Edmonds–Karp는 매번 BFS로 간선 수 기준 최단 잔여 경로를 선택합니다. 이 선택 덕분에 어떤 간선이 최단 경로의 병목으로 포화된 뒤 다시 중요해지려면 s에서 해당 간선까지 또는 그 이후 거리가 증가해야 하고, 한 간선의 임계적 사용 횟수가 제한됩니다. 전체 증가 횟수는 O(VE)로 제한되고, 매번 BFS와 인접 간선 검사가 O(E)이므로 O(VE²) 상한이 나옵니다.
이 상한은 capacity의 숫자 크기에 직접 비례하는 F번 증가 같은 표현이 아닙니다. 큰 정수 capacity를 binary search로 다루는 구현을 뜻하지도 않습니다. BFS 층의 변화와 포화 edge의 재등장 횟수로 분석하는 그래프 크기 기반 상한입니다. 반대로 DFS로 임의 경로를 고르면서 Edmonds–Karp 상한을 그대로 쓰거나, 각 BFS에서 잔여 edge를 중복 스캔하는 자료구조 비용을 누락하면 주장 범위가 어긋납니다.
구현 선택과 검증
먼저 입력 edge와 residual edge의 ID를 분리하고, 양방향으로 보이는 간선이 원래 간선인지 역간선인지 추적 가능하게 합니다. 각 augment 뒤에는 모든 원래 간선에서 0≤flow≤capacity, 중간 정점의 보존, flow value = source outflow = sink inflow를 검사합니다. 작은 그래프에서는 가능한 cut을 모두 계산해 flow가 그보다 크지 않은지도 확인할 수 있습니다.
설명용 trace로 위 네트워크에서 s-u-v-t에 1을 먼저 보내고, 이후 s-v→reverse(u-v)→u-t를 따라가 보십시오. 첫 경로만 저장한 구현은 두 번째 선택에서 멈추지만 residual 구현은 취소와 전진을 함께 갱신해야 합니다. 최종 BFS에서 S와 T를 표시하고 원래 S→T 간선의 capacity 합과 flow 값을 대조하면 종료·최적성·최소 컷을 한 번에 검사할 수 있습니다.
참고 자료와 검증 범위
- Maximum flow - Ford-Fulkerson and Edmonds-Karp — cp-algorithms, 2026-09-18 갱신본의 본문을 2026-09-19 확인했습니다. residual reverse edge, no residual path, max-flow/min-cut, Edmonds–Karp
O(VE²)주장의 근거로 사용했습니다. - BFS의 층별 탐색과 최단 거리 — 저장소 노트의 큐 층 불변식을 Edmonds–Karp BFS의 구현 전제로 대조했습니다.
- 숫자 네트워크 trace는 설명용 계산입니다. 이 batch에서 flow 구현을 실행한 결과나 특정 라이브러리의 동작 측정으로 제시하지 않습니다.