최대 유량과 Ford-Fulkerson

Fluss(flow)는 각 간선에서 \(0 \le f(u,v) \le c(u,v)\)0 ≤ f(u,v) ≤ c(u,v)를 지키고, 내부 정점 v in V - {s,t}에서는 유입량과 유출량이 같다. Ford-Fulkerson은 \(\text{residual} \text{graph} G_{f}\)residual graph G_f에서 augmenting s-t path를 찾고, 병목 residual capacity만큼 flow를 늘리거나 되돌린다. 더 이상 augmenting path가 없으면 Max-Flow Min-Cut Theorem에 의해 현재 flow가 maximum이다.

\(|f| = \sum_{v} f(s,v) - \sum_{v} f(v,s)\)|f| = sumᵥ f(s,v) - sumᵥ f(v,s). Residual capacity는 원래 방향이면 c(u,v)-f(u,v), 반대 방향이면 f(v,u)로 생긴다.

문장에 'defined by capacity sum', 'immer weniger Kanten', 'kein Pfad', 'eingehender vs. ausgehender Fluss'가 나오면 flow value, residual graph, conservation을 각각 분리해서 판정한다.

• II-12

II부에서는 올바른 진술을 정확히 2개 골라야 하며, II-12는 2점 문항이다.

정답 위치를 외우는 것이 아니라 capacity, 실제 flow, residual graph, augmenting path, conservation을 따로 검사하는 절차를 익힌다.

시험 복기 자료(Gedächtnisprotokoll)는 재구성 자료이지 공식 정답지가 아니다. 로컬 Markdown의 독일어 움라우트가 깨져 있어 의미가 명확한 부분만 복원했다.

최대 유량 문제는 파이프의 최대 굵기(capacity)가 아니라 실제로 흘려보낸 양(flow)을 다룬다. Ford-Fulkerson의 핵심은 이미 보낸 결정을 residual graph에서 되돌릴 수 있게 표현하는 것이다. 그래서 residual graph에는 원래 간선의 남은 여유뿐 아니라, 이전에 보낸 flow를 취소하는 역방향 여유가 생긴다.

유량 네트워크(Flussnetzwerk)는 방향 그래프 \(G=(V,E),\)G=(V,E),음이 아닌 용량 c, 소스 s, 싱크 t로 이루어진다. 유량 f는 모든 간선에서 \(0 \le f(u,v) \le c(u,v)\)0 ≤ f(u,v) ≤ c(u,v)를 지키고, s와 t를 제외한 모든 내부 정점 v에서 유량 보존을 만족해야 한다. 유량값 |f|는 s에서 순수하게 빠져나가는 양이며, 유량 보존이 성립하면 t로 순수하게 들어오는 양과 같다. 잔여 그래프\((\text{residual} \text{graph}) G_{f}\)(residual graph) G_f에는 잔여 용량 \(c_{f}(u,v) > 0\)c_f(u,v) > 0인 방향 쌍만 들어간다. 증가 경로(augmenting path)는 \(G_{f}\)G_f안의 s-t 경로이며, 그 경로의 병목 잔여 용량만큼 현재 유량을 늘릴 수 있다.

• 간선 방향이 있는 graph를 읽을 수 있어야 한다.
• capacity c와 flow f를 같은 숫자로 착각하지 않아야 한다.
• cut capacity c(S,V-S)는 S에서 V-S로 나가는 capacity의 합이라는 점을 알아야 한다.

용량 제약(capacity constraint)은 모든 간선에서 \(0 \le f(u,v) \le c(u,v)\)0 ≤ f(u,v) ≤ c(u,v)를 요구한다. 유량 보존(flow conservation)은 \(v \in V - \{s,t\}\)v ∈ V - {s,t}인 모든 내부 정점에서 유입량의 합과 유출량의 합이 같다는 뜻이다. \(f(u,v) > 0\)f(u,v) > 0이면 \(G_{f}\)G_f에 잔여 용량 f(u,v)를 가진 역방향 간선 (v,u)가 생길 수 있다. 마지막으로 \(G_{f}\)G_f에 증가 s-t 경로가 없을 때 그리고 그때에만 f가 최대 유량이며, |f|는 최소 컷 용량과 같다.

강의에서 기본 Ford-Fulkerson의 실행시간은 \(O(|E| \cdot u \cdot |f\cdot |)\)O(|E| * u * |f*|)이다. 한 반복에서 유량이 최소 1/u만큼만 증가할 수도 있기 때문이다. 증가 경로를 BFS로 고르는 Edmonds-Karp 개선의 실행시간은 \(O(|V| \cdot |E|^2)\)O(|V| * |E|²)이다. 잔여 그래프에는 역방향·역평행 간선이 생길 수 있으므로 원래 네트워크보다 방향 간선 수가 많아질 수도 있다.

t로 들어오는 간선 용량의 합은 최대 유량의 정의가 아니라 상한일 뿐이다. s 근처에 작은 병목이 있으면 최대 유량은 t로 들어오는 전체 용량보다 훨씬 작을 수 있다. 잔여 그래프의 간선 수는 현재 유량에 따라 원래 그래프와 같거나 더 적거나 더 많을 수 있다. 또한 임의의 실수 용량과 임의의 경로 선택을 허용하면 교과서의 Ford-Fulkerson 종료성에 주의해야 한다. II-12의 진술은 강의 의사코드의 반복 종료 조건과 최적성 기준으로 읽는다.

• definiert
• Summe der Kapazität
• terminiert
• kein flusserhöhender Pfad
• immer
• weniger Kanten
• eingehender Fluss
• ausgehender Fluss

유량(flow)은 용량 제약과 유량 보존을 모두 만족해야 한다. Ford-Fulkerson은 \(G_{f}\)G_f에서 s-t 증가 경로를 반복해서 찾고 그 경로의 병목만큼 유량을 늘린다.

강의의 기본 실행시간은 \(O(|E| \cdot u \cdot |f\cdot |)\)O(|E| * u * |f*|)이고, Edmonds-Karp 개선은 \(O(|V| \cdot |E|^2)\)O(|V| * |E|²)이다.

잔여 그래프에는 역방향·역평행 간선이 생길 수 있으므로 '항상 원래 그래프보다 간선이 적다'는 말은 거짓이다.

각 선택지가 용량 c, 유량 f, 원래 그래프 G, 잔여 그래프 \(G_{f}\)G_f중 무엇을 말하는지 먼저 표시한다. 그다음 정의, 보존 법칙, 잔여 간선 규칙, 최대 유량-최소 컷 정리를 적용한다.