본문으로 건너뛰기
SuanLab

그래프 탐색·유량·최소 컷 증명서

잔여 그래프를 실제 탐색하고 최적성 증거를 확인합니다.

298 / ALGORITHMS AND COMPUTATION LAB
먼저 알아두면 좋아요 · 연결된 선수 단원의 이산수학·확률·선형대수·계산 기초
그래프·트리·DAG →약·강 쌍대성과 Slater 반례 →
단원 목록 (600) · 그래프 탐색·유량·최소 컷 증명서
이해하는 속도로 읽으세요.개념도이론실험확인 문제
BUILD YOUR INTUITION

먼저 그림으로 이해하기

한 번에 한 단계씩 살펴보세요.

잔여 그래프를 실제 탐색하고 최적성 증거를 확인합니다.

Four-node directed integral network with BFS augmenting paths in the actual residual graph, including reverse residual edges. The augmentation limit may stop before optimality. Upper edge labels are current flow/capacity on original arcs; orange nodes are currently residual-reachable from s. Blue flow after each augmentation, orange exhaustive minimum s-t cut capacity. A reachable set is a valid cut certificate only when t is unreachable.

3/32/21/12/23/3sabt
실제 선택한 유한 그래프입니다. 방향 화살표는 원래 flow arc, flow 숫자는 현재 유량/용량입니다. 다른 그래프의 주황 표시는 선택 mask나 현재 값을 해석하는 본문·표를 따르세요. 위치와 선 길이는 비용이 아닙니다.
035.250
가로 augmentation 횟수 · 파랑 현재 유량 · 주황 전수 계산한 최소 컷 용량
original arcflowcapacityforward residual
s->a330
s->b220
a->b110
a->t220
b->t330

current feasible flow value = 5

고정 기준 예제의 그림과 수치입니다. 각 단계에서 같은 그림의 의미를 차례로 살펴보세요. 고정된 기준 예제이며 아래 실험의 설정과 독립적입니다.
1 / 4

허용 유량

각 arc의 용량과 내부 node의 보존을 확인합니다.

0<=f<=c

실험에서 확인하기 →
이 단원 목차

탐색 결과에서 최적성 증거로

s에서 t까지 보낼 수 있는 최대 흐름을 구합니다. Arc에는 용량이 있고 내부 node에서는 들어오는 양과 나가는 양이 같아야 합니다. 이 단원은 네 node와 다섯 방향 arc를 사용하여 실제 BFS, 병목 갱신, 잔여 도달 집합과 컷을 계산합니다. 작은 그래프이므로 가능한 네 개 s-t 컷도 별도로 전수 계산할 수 있습니다.

위 그림의 숫자는 현재 유량/용량입니다. 주황 node는 잔여 그래프에서 s로부터 도달하는 node입니다. 그 집합에 t까지 포함되면 아직 s-t 컷 증명서가 아닙니다. 파랑 그래프는 실제 augmentation 뒤의 유량, 주황 기준선은 전수 계산한 최소 컷 용량입니다.

가능성과 잔여 용량

0≤fij≤cij,∑jfij−∑jfji=0(i≠s,t).0\le f_{ij}\le c_{ij},\qquad \sum_j f_{ij}-\sum_j f_{ji}=0\quad(i\ne s,t).

구현은 skew-symmetric net flow F를 저장하여 Fji=-Fij로 둡니다. 원래 arc의 추가 여유는 Cij-Fij이고, 원래 없던 역방향은 이미 보낸 유량을 되돌릴 기회를 나타냅니다. 역 arc를 지우면 초기 선택을 고칠 수 없는 다른 알고리즘이 됩니다. 그림은 원래 arc만 표시하며 잔여 탐색은 역방향도 포함합니다.

BFS는 양의 잔여 용량인 arc로만 이동합니다. 경로를 찾으면 최소 잔여 용량 delta를 계산해 모든 경로 arc에 더하고 역방향에서 뺍니다. 정수 용량에서는 현재 작은 예제의 유량도 정수입니다. 더 일반적인 termination과 Edmonds–Karp 복잡도는 BFS의 최단 경로 성질을 사용해 별도로 분석합니다.

왜 컷이 상한인가

S가 s를 포함하고 t를 제외한다고 합시다. 내부 node 보존식을 더하면 내부 arc가 상쇄되어 순유출은 전체 유량 값입니다.

∣f∣=∑i∈S,j∉Sfij−∑i∉S,j∈Sfij≤∑i∈S,j∉Scij=c(S,Sˉ).|f|=\sum_{i\in S,j\notin S}f_{ij}-\sum_{i\notin S,j\in S}f_{ij} \le\sum_{i\in S,j\notin S}c_{ij}=c(S,\bar S).

잔여 탐색에서 t가 도달 불가능하면 S의 바깥 방향 arc는 모두 포화이고 반대 방향 유량은 0입니다. 따라서 부등식이 등식이 되어 현재 유량과 컷이 서로 최적임을 증명합니다. 단지 실행 상한에 도달한 것은 이 조건을 대신하지 못합니다.

손계산과 직접 풀기

용량을 s→a=3, s→b=2, a→b=1, a→t=2, b→t=3으로 두세요. BFS는 s-a-t에 2, s-b-t에 2를 보내고, 마지막 s-a-b-t에 1을 보냅니다. 총 5이며 source 밖 용량 3+2도 5이므로 더 클 수 없습니다.

직접 풀기: augmentation을 한 번만 허용하면 최대 유량인가요? 풀이: 현재 값은 2이고 s-b-t 같은 잔여 경로가 남습니다. UI는 최적성 flag를 0, 도달 컷 증명값을 미정으로 표시해야 합니다. 유효한 중간 유량과 최적해를 구분하세요. 모든 용량 0이면 값 0과 컷 0이 이미 일치합니다.

AI 최적화의 증명서

Matching, assignment, routing 문제에서는 목적값뿐 아니라 feasibility와 상한·하한의 일치가 중요합니다. Learned optimizer가 낸 후보도 원래 용량·보존식으로 검증할 수 있습니다. 이 유한 예제에서 전수 컷 계산은 독립 oracle이며 큰 그래프를 위한 효율적인 방법 자체로 주장하지 않습니다. 검증 가능한 증거와 단순히 좋아 보이는 점수를 분리하세요.

참고: MIT 그래프 알고리즘 자료.

CHECK YOUR UNDERSTANDING

설명할 수 있나요?

실험 설정과 무관한 기준 예제를 묻습니다. 답을 고르고 설명을 확인해보세요.

1. 반복 상한에 도달하면 자동으로 최대 유량인가요?
2. 가능 유량 값은 모든 s-t 컷 용량 이하인가요?

선택한 답과 학습 표시는 이 브라우저에 저장됩니다. 다시 풀거나 표시를 해제할 수 있습니다.