최대 유량 (Max Flow)

최대 유량 (Max Flow)

네트워크에서 소스(Source)에서 싱크(Sink)까지 흐를 수 있는 최대 유량을 찾는 문제로, Ford-Fulkerson 방법과 Edmonds-Karp 알고리즘 등을 사용하여 잔여 그래프(Residual Graph)에서 증가 경로를 반복적으로 찾아 해결

목적: 네트워크 용량 최대화, 자원 할당, 이분 매칭, 병목 분석

특징: 유량 보존, 용량 제약, 잔여 그래프, 증가 경로

구성요소: 소스(s), 싱크(t), 간선 용량(c), 유량(f), 잔여 용량(c - f)

유량 제약: ① 용량 제약(0 ≤ f(u,v) ≤ c(u,v)) ② 유량 보존(들어오는 유량 = 나가는 유량, s/t 제외)

Ford-Fulkerson 방법: 증가 경로 존재 시 반복 → DFS/BFS로 경로 찾기 → 최소 잔여 용량만큼 유량 증가

Edmonds-Karp 알고리즘: Ford-Fulkerson + BFS(최단 증가 경로), O(VE²) 시간 복잡도 보장

잔여 그래프(Residual Graph): 잔여 용량 c(u,v) - f(u,v) + 역방향 간선 f(u,v)

최대 유량-최소 컷 정리: 최대 유량 = 최소 컷 용량

시간 복잡도: Ford-Fulkerson O(E × max_flow), Edmonds-Karp O(VE²), Dinic O(V²E), Push-Relabel O(V³)

공간 복잡도: O(V + E)

장점: 다양한 응용, 최적해 보장, 이론적 우아함

단점: 높은 시간 복잡도, 실수 용량 시 종료 안 될 수 있음

적용사례: 네트워크 트래픽, 이분 매칭, 프로젝트 선택, 이미지 세그멘테이션, 항공편 스케줄링

비교: Ford-Fulkerson(DFS/BFS) vs Dinic(레벨그래프) vs Push-Relabel(사전유량)

연관: 네트워크 플로우, 최소 컷, 이분 매칭, 증가 경로, 잔여 그래프