한 번에 많이 보내는 길부터 채우면, 전체도 가장 많이 보낼까요?

통로 하나를 넓히면 보낼 수 있는 최대량은 줄지 않아요. 그렇지만 “지금 한 번에 가장 많이 보낼 수 있는 길부터 채우기”라는 배정 규칙의 결과도 좋아질까요? 전체 최적값과 특정 규칙의 출력은 따로 계산해야 해요.

자체 방향 통로는 아래 다섯 개뿐이에요. 용량은 같은 시간단위의 최대 연속량이에요. 중간점에 저장·손실이 없어 들어온 양과 나간 양이 같아요. 이미 배정한 양은 줄이지 않는다고 정해요.

p≥2q>0,c>q입니다. 규칙은 남은 원방향 경로 중 한 번에 추가할 수 있는 양이 가장 큰 것을 택해 그 양만큼 채워요. 최초 교차 경로 S→A→B→T의 폭 x=min(p,c)는 q보다 크므로 먼저 선택돼요. 이후 두 바깥 경로는 각각 min(q,p−x)만큼만 남아요.

그다음에는 원방향으로 더 추가할 경로가 없어요. 하지만 이전 배정을 줄이지 않았다는 조건까지 포함한 종료다.

전체 최대 M은 별도로 구해요. S에서 나가는 두 통로의 합 때문에 M≤p+q입니다. 또 S와 A를 한쪽에 놓으면 그 밖으로 나가는 A→T,S→B,A→B의 용량 합이 2q+c라 M≤2q+c입니다. 이 두 상한만 적고 최대라고 끝내지는 않아요.

교차에 z=min(c,p−q)를 배정하고 두 바깥 경로에는 q씩 넣으면 실제 가능해요. 큰 두 통로의 사용량 q+z가 p 이하이고, 모든 중간점의 보존도 맞아요. 따라서

이 가족에서는 일반 최대유량 정리를 다시 증명하지 않고 상한과 달성 배정을 직접 맞췄어요.

q<c≤p−q이면 규칙도 2q+c를 얻어요. 반면 c>p−q에서는 G=2p−min(p,c),M=p+q입니다. c가 p−q를 넘어 p까지 늘어날 때 최적값은 일정하지만 규칙 출력은 감소해요.

p=3,q=1에서 c=2이면 둘 다4입니다. c=3으로 넓히면 규칙은 교차에3을 먼저 넣어 두 바깥 경로를 막으므로3에서 끝나요. 실제 최대는 여전히4입니다. 통로 확대 자체가 최대량을 줄인 것은 아니에요.

부족량 d=min(p,c)+q−p가 양수라면 기존 교차 배정을 d만큼 줄이고 S→B와 A→T의 배정을 각각 d 늘려요. 보존·용량을 지키며 총량을 d 늘려 최대에 도달해요. 원 그래프에 B→A 통로를 새로 만든 것이 아니에요. 배정표에서 이전 선택의 일부를 취소했어요.

Erickson은 이 감산 가능성을 residual 역방향으로 표현해요. 교사는 “추가할 길이 없다”라는 답에 어느 선택까지 수정할 수 있는지 묻게 해요. 실제 물류 기록이나 혼잡 비용의 균형을 분석한 사례는 아니며, 정한 연속량·용량·배정 규칙 안에서 증명한 결과예요.

출처·착안: Jeff Erickson, Algorithms, Chapter10: Maximum Flows and Minimum Cuts. 질문·조건·표·증명은 원문의 관점에서 새로 구성했다.