II-12 Max Flow·Residual Graph·유량 보존 — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
Capacity는 도로의 최대 폭이고 flow는 실제로 흐르는 양입니다. 최대 유량은 t로 들어오는 capacity 총합 그 자체가 아니라 제약 아래 실제로 보낼 수 있는 최댓값입니다.
도시 입구 도로 폭의 합이 크더라도 중간의 좁은 다리가 실제 공급량을 제한합니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. A는 bound와 value, B는 종료조건, C는 reverse edge, D는 conservation으로 분리합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
Capacity는 도로의 최대 폭이고 flow는 실제로 흐르는 양입니다. 최대 유량은 t로 들어오는 capacity 총합 그 자체가 아니라 제약 아래 실제로 보낼 수 있는 최댓값입니다.
이 문항에서 가장 먼저 붙잡을 문장은 'capacity \(\sum \text{into} t\)sum into t는 upper bound일 뿐 max-flow 정의값과 항상 같지 않다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- capacity \(\sum \text{into} t\)
sum into t는 upper bound일 뿐 max-flow 정의값과 항상 같지 않다. - A는 bound와 value, B는 종료조건, C는 reverse edge, D는 conservation으로 분리합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, capacity \(\sum \text{into} t\)sum into t는 upper bound일 뿐 max-flow 정의값과 항상 같지 않다. 둘째, residual graph의 augmenting path가 없으면 Ford-Fulkerson이 종료한다.
셋째, residual reverse edges 때문에 간선 수가 원래보다 늘 수 있다. 넷째, 내부 정점에서는 \(\text{inflow}=\text{outflow}\)inflow=outflow라는 conservation이 성립한다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- capacity \(\sum \text{into} t\)
sum into t는 upper bound일 뿐 max-flow 정의값과 항상 같지 않다. - residual graph의 augmenting path가 없으면 Ford-Fulkerson이 종료한다.
- residual reverse edges 때문에 간선 수가 원래보다 늘 수 있다.
- 내부 정점에서는 \(\text{inflow}=\text{outflow}\)
inflow=outflow라는 conservation이 성립한다.
개념 3 · 강의 정의를 초보자 언어로 해체
최대 유량 문제는 파이프의 최대 굵기(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 경로이며, 그 경로의 병목 잔여 용량만큼 현재 유량을 늘릴 수 있다.
수식으로 정확히 쓰기
핵심 규칙\(|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)로 생긴다.
이 절에서 꼭 기억할 것
- 간선 방향이 있는 graph를 읽을 수 있어야 한다.
- capacity c와 flow f를 같은 숫자로 착각하지 않아야 한다.
- cut capacity c(S,V-S)는 S에서 V-S로 나가는 capacity의 합이라는 점을 알아야 한다.
개념 4 · 성립 조건·불변식·경계 사례
용량 제약(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|는 최소 컷 용량과 같다.
t로 들어오는 간선 용량의 합은 최대 유량의 정의가 아니라 상한일 뿐이다. s 근처에 작은 병목이 있으면 최대 유량은 t로 들어오는 전체 용량보다 훨씬 작을 수 있다. 잔여 그래프의 간선 수는 현재 유량에 따라 원래 그래프와 같거나 더 적거나 더 많을 수 있다. 또한 임의의 실수 용량과 임의의 경로 선택을 허용하면 교과서의 Ford-Fulkerson 종료성에 주의해야 한다. II-12의 진술은 강의 의사코드의 반복 종료 조건과 최적성 기준으로 읽는다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
강의에서 기본 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|²)이다. 잔여 그래프에는 역방향·역평행 간선이 생길 수 있으므로 원래 네트워크보다 방향 간선 수가 많아질 수도 있다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 B, D입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: B, D
이 절에서 꼭 기억할 것
- A와 C는 용량 또는 잔여 표현을 실제 유량과 혼동한다. B와 D는 강의에서 제시한 종료 조건과 유량 보존을 그대로 적용한 진술이다.
- A: 용량 합은 상한일 뿐이다. B: 증가 경로가 없으면 멈춘다. C: 잔여 역방향 간선 때문에 간선 수가 늘 수 있다. D: 내부 정점의 유량 보존으로 들어오는 합과 나가는 합이 같다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
Max Flow·Residual Graph·유량 보존
capacity \(\sum \text{into} t\)sum into t는 upper bound일 뿐 max-flow 정의값과 항상 같지 않다. | residual graph의 augmenting path가 없으면 Ford-Fulkerson이 종료한다. | residual reverse edges 때문에 간선 수가 원래보다 늘 수 있다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
최대 유량과 Ford-Fulkerson에 대한 설명 중 정확히 두 개를 고르시오.
핵심 규칙Max Flow·Residual Graph·유량 보존
핵심 도구를 종이에 꺼낸다
A는 bound와 value, B는 종료조건, C는 reverse edge, D는 conservation으로 분리합니다.
핵심 규칙capacity \(\sum \text{into} t\)
sum into t는 upper bound일 뿐 max-flow 정의값과 항상 같지 않다. | residual graph의 augmenting path가 없으면 Ford-Fulkerson이 종료한다. | residual reverse edges 때문에 간선 수가 원래보다 늘 수 있다.선택지 A를 독립 판정한다
강의에서 flow value |f|는 source s의 net outflow로 정의된다. conservation 때문에 sink t의 net inflow와 같지만, t로 들어오는 capacity의 합은 가능한 상한일 뿐이다. 그 cut이 minimum cut이고 해당 edge들이 포화될 때만 값이 같을 수 있다.
\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
강의 의사코드는 잔여 그래프(residual graph)에서 s부터 t까지 경로가 있는 동안 반복한다. 따라서 증가 경로(augmenting path)가 없으면 반복 조건이 거짓이 되어 멈춘다. 최대 유량-최소 컷 정리(Max-Flow Min-Cut Theorem)도 '증가 경로가 없음'과 '최대 유량'을 동치로 둔다.
\[선택지 B = 참\]선택지 B = 참선택지 C를 독립 판정한다
Residual graph에는 남은 forward capacity가 있으면 원래 방향 edge가 들어가고, 이미 보낸 flow가 있으면 reverse direction edge도 들어간다. 강의는 residual graph에서 antiparallel edges가 허용된다고 명시한다. 따라서 간선 수가 더 많아질 수 있다.
\[선택지 C = 거짓\]선택지 C = 거짓선택지 D를 독립 판정한다
flow conservation은 내부 정점에서 total incoming flow와 total outgoing flow가 정확히 같다고 말한다. 따라서 'incoming이 outgoing보다 클 수 없다'는 약한 형태의 문장은 참이다.
\[선택지 D = 참\]선택지 D = 참정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 B, D입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = B, D\]검증된 정답 = B, D
2. 이 문제를 실제로 끝까지 풀기
Capacity는 도로의 최대 폭이고 flow는 실제로 흐르는 양입니다. 최대 유량은 t로 들어오는 capacity 총합 그 자체가 아니라 제약 아래 실제로 보낼 수 있는 최댓값입니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) capacity \(\sum \text{into} t\)sum into t는 upper bound일 뿐 max-flow 정의값과 항상 같지 않다. (2) residual graph의 augmenting path가 없으면 Ford-Fulkerson이 종료한다. (3) residual reverse edges 때문에 간선 수가 원래보다 늘 수 있다. (4) 내부 정점에서는 \(\text{inflow}=\text{outflow}\)inflow=outflow라는 conservation이 성립한다.
선택지 A는 거짓입니다. 강의에서 flow value |f|는 source s의 net outflow로 정의된다. conservation 때문에 sink t의 net inflow와 같지만, t로 들어오는 capacity의 합은 가능한 상한일 뿐이다. 그 cut이 minimum cut이고 해당 edge들이 포화될 때만 값이 같을 수 있다. 가장 작은 확인 예는 \(s\to a\)s→a의 용량이 \(1, a\to t\)1, a→t와 \(b\to t\)b→t의 용량이 각각 100이라고 하자. b가 s에서 도달 불가능하면 t로 들어오는 용량 합은 200이어도 최대 s-t 유량은 1 이하다.
선택지 B는 참입니다. 강의 의사코드는 잔여 그래프(residual graph)에서 s부터 t까지 경로가 있는 동안 반복한다. 따라서 증가 경로(augmenting path)가 없으면 반복 조건이 거짓이 되어 멈춘다. 최대 유량-최소 컷 정리(Max-Flow Min-Cut Theorem)도 '증가 경로가 없음'과 '최대 유량'을 동치로 둔다.
선택지 C는 거짓입니다. Residual graph에는 남은 forward capacity가 있으면 원래 방향 edge가 들어가고, 이미 보낸 flow가 있으면 reverse direction edge도 들어간다. 강의는 residual graph에서 antiparallel edges가 허용된다고 명시한다. 따라서 간선 수가 더 많아질 수 있다. 가장 작은 확인 예는 원래 간선이 용량 2인 \(s\to t\)s→t하나이고 현재 유량이 1이면, 잔여 그래프에는 용량 1인 \(s\to t\)s→t와 \(t\to s\)t→s가 생긴다. 원래 그래프는 간선 1개지만 잔여 그래프는 방향 간선 2개다.
선택지 D는 참입니다. flow conservation은 내부 정점에서 total incoming flow와 total outgoing flow가 정확히 같다고 말한다. 따라서 'incoming이 outgoing보다 클 수 없다'는 약한 형태의 문장은 참이다.
따라서 현재 문언에서 참으로 검증된 선택지는 B, D입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. A는 bound와 value, B는 종료조건, C는 reverse edge, D는 conservation으로 분리합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
강의에서 flow value |f|는 source s의 net outflow로 정의된다. conservation 때문에 sink t의 net inflow와 같지만, t로 들어오는 capacity의 합은 가능한 상한일 뿐이다. 그 cut이 minimum cut이고 해당 edge들이 포화될 때만 값이 같을 수 있다.
빠른 확인법: \(s\to a\)
s→a의 용량이 \(1, a\to t\)1, a→t와 \(b\to t\)b→t의 용량이 각각 100이라고 하자. b가 s에서 도달 불가능하면 t로 들어오는 용량 합은 200이어도 최대 s-t 유량은 1 이하다. -
B참 — 정답 후보
강의 의사코드는 잔여 그래프(residual graph)에서 s부터 t까지 경로가 있는 동안 반복한다. 따라서 증가 경로(augmenting path)가 없으면 반복 조건이 거짓이 되어 멈춘다. 최대 유량-최소 컷 정리(Max-Flow Min-Cut Theorem)도 '증가 경로가 없음'과 '최대 유량'을 동치로 둔다.
빠른 확인법: 더 이상 flow를 증가시키는 경로가 존재하지 않으면 알고리즘은 종료한다.
-
C거짓
Residual graph에는 남은 forward capacity가 있으면 원래 방향 edge가 들어가고, 이미 보낸 flow가 있으면 reverse direction edge도 들어간다. 강의는 residual graph에서 antiparallel edges가 허용된다고 명시한다. 따라서 간선 수가 더 많아질 수 있다.
빠른 확인법: 원래 간선이 용량 2인 \(s\to t\)
s→t하나이고 현재 유량이 1이면, 잔여 그래프에는 용량 1인 \(s\to t\)s→t와 \(t\to s\)t→s가 생긴다. 원래 그래프는 간선 1개지만 잔여 그래프는 방향 간선 2개다. -
D참 — 정답 후보
flow conservation은 내부 정점에서 total incoming flow와 total outgoing flow가 정확히 같다고 말한다. 따라서 'incoming이 outgoing보다 클 수 없다'는 약한 형태의 문장은 참이다.
빠른 확인법: v in V \ {s,t}인 내부 정점은 유출 flow보다 더 많은 유입 flow를 가질 수 없다.
4. 초보자가 가장 자주 틀리는 이유
- A와 C는 용량 또는 잔여 표현을 실제 유량과 혼동한다. B와 D는 강의에서 제시한 종료 조건과 유량 보존을 그대로 적용한 진술이다.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
A는 bound와 value, B는 종료조건, C는 reverse edge, D는 conservation으로 분리합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 B, D이다. 핵심 근거: capacity \(\sum \text{into} t\)sum into t는 upper bound일 뿐 max-flow 정의값과 항상 같지 않다. residual graph의 augmenting path가 없으면 Ford-Fulkerson이 종료한다. residual reverse edges 때문에 간선 수가 원래보다 늘 수 있다. 내부 정점에서는 \(\text{inflow}=\text{outflow}\)inflow=outflow라는 conservation이 성립한다.
6. 스스로 이해했는지 확인
II-12의 주제를 한 문장으로 설명하면?
정답: Capacity는 도로의 최대 폭이고 flow는 실제로 흐르는 양입니다. 최대 유량은 t로 들어오는 capacity 총합 그 자체가 아니라 제약 아래 실제로 보낼 수 있는 최댓값입니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: A는 bound와 value, B는 종료조건, C는 reverse edge, D는 conservation으로 분리합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: capacity \(\sum \text{into} t\)sum into t는 upper bound일 뿐 max-flow 정의값과 항상 같지 않다.
핵심 사실 네 가지 중 두 번째는?
정답: residual graph의 augmenting path가 없으면 Ford-Fulkerson이 종료한다.
가장 위험한 함정은?
정답: A와 C는 용량 또는 잔여 표현을 실제 유량과 혼동한다. B와 D는 강의에서 제시한 종료 조건과 유량 보존을 그대로 적용한 진술이다.
정답 label은?
정답: B, D
flow f의 두 가지 핵심 조건을 말하라.
정답: 모든 edge/pair에 대해 \(0 \le f(u,v) \le c(u,v)\)0 ≤ f(u,v) ≤ c(u,v)를 만족하고, 모든 내부 정점 v in V - {s,t}에서 incoming flow와 outgoing flow가 같다.
flow value |f|는 무엇으로 정의되는가?
정답: source s의 net outflow, 즉 \(\sum_{v} f(s,v) - \sum_{v} f(v,s)\)sumᵥ f(s,v) - sumᵥ f(v,s)로 정의된다. conservation이 있으면 sink t의 net inflow와 같다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-12
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· MC section II-12
복원된 시험 문항 II-12의 문제 문장과 원래 선택지 네 개를 뒷받침한다.Vorlesung\06GraphAlgorithms.pdf· pp. 181-183
유량 네트워크 정의, 용량 제약 \(0 \le f(u,v) \le c(u,v), v\in V - \{s,t\}\)0 ≤ f(u,v) ≤ c(u,v), v ∈ V - {s,t}에 대한 유량 보존, 유량값 |f|를 뒷받침한다.Vorlesung\06GraphAlgorithms.pdf· pp. 184-188
Ford-Fulkerson이 잔여 그래프에서 증가 경로를 찾고, 잔여 용량에는 정방향과 역방향이 포함되며, 잔여 그래프에 s-t 경로가 없을 때 반복을 멈춘다는 내용을 뒷받침한다.Vorlesung\06GraphAlgorithms.pdf· pp. 193-194
최대 유량-최소 컷 정리에 따라 최대 유량, \(G_{f}\)G_f에 증가 경로가 없음, 최소 컷 용량이 서로 동치라는 내용을 뒷받침한다.