네트워크 플로우 계산기 (최대 유량)

네트워크 플로우 계산기 (최대 유량) 정보

네트워크 플로우 계산기는 용량이 설정된 모든 유향 네트워크에서 선택한 소스 s부터 싱크 t까지의 최대 유량을 계산합니다. 내부적으로는 너비 우선 증가 경로(Edmonds-Karp 알고리즘)를 사용하는 Ford-Fulkerson 방법을 실행하며, 발견된 모든 경로를 기록하여 전체 결정 과정을 하나씩 다시 재생해 볼 수 있습니다. 또한 결과 페이지에는 유량값이 최적임을 증명하는 병목 분할인 최소 컷(Min-cut)이 표시됩니다.

최대 유량 문제란 무엇인가요?

유량 네트워크는 유향 그래프 G = (V, E)와 용량 함수 c: E → ℝ_≥0로 구성됩니다. 두 개의 특수한 정점이 정의되는데, 유량이 시작되는 소스 s와 유량이 소비되는 싱크 t입니다. 유량 f는 다음 규칙을 준수하며 간선에 할당된 값 f(u, v) ≥ 0입니다.

최대 유량 문제는 |f|를 최대화하는 유량 f를 찾는 것입니다. 직관적으로 설명하자면, 간선이 주어진 용량의 수도관일 때 s에서 t로 초당 보낼 수 있는 최대 리터 수는 얼마인지를 구하는 것입니다.

알고리즘 작동 원리 — BFS 기반 Ford-Fulkerson

이 알고리즘은 현재 유량과 함께 잔여 그래프를 유지합니다. 용량이 c이고 현재 유량이 f인 모든 간선 (u, v)에 대해 잔여 그래프는 다음을 포함합니다.

• 순방향 잔여 간선 (u, v): 용량 c − f (얼마나 더 보낼 수 있는가)
• 역방향 잔여 간선 (v, u): 용량 f (이미 보낸 유량을 얼마나 취소할 수 있는가)

각 반복에서 잔여 그래프 상의 s에서 t까지 너비 우선 탐색(BFS)을 수행합니다. 경로가 발견되면 해당 경로의 최소 간선 용량(병목)을 모든 순방향 간선 유량에 더하고, 모든 역방향 간선 유량에서 뺍니다. 이를 증가 경로라고 합니다. BFS가 더 이상 t에 도달할 수 없으면 현재 유량이 최적입니다.

임의의 경로 찾기 대신 BFS를 사용하면 Ford-Fulkerson은 Edmonds-Karp 알고리즘이 되며, O(V · E²)의 실행 시간이 보장됩니다. 또한 일반 Ford-Fulkerson과 달리 무리수 용량에서도 종료가 보장됩니다.

최대 유량 최소 컷 정리

컷은 정점들을 s ∈ S이고 t ∈ T인 두 집합 (S, T)로 나누는 것입니다. 컷의 용량은 S에서 T로 가는 간선들의 용량 합입니다.

최대 유량 최소 컷 정리(Ford & Fulkerson, 1956)에 따르면 다음과 같습니다.

이 도구는 최소 컷을 자동으로 찾습니다. Edmonds-Karp가 종료된 후 잔여 그래프에서 s로부터 다시 한번 BFS를 실행합니다. 도달 가능한 정점들이 S를 형성하고 나머지가 T를 형성하며, 원래 그래프에서 S → T를 가로지르는 모든 간선은 포화 상태가 됩니다. 이들의 용량 합은 최대 유량값과 정확히 일치하며, 결과 상단의 "최소 컷 용량 ✓ 최적성 확인"에서 이를 확인할 수 있습니다.

학습을 위해 설계된 기능

• 단계별 애니메이션. 재생, 일시정지 및 단계별 컨트롤을 통해 모든 증가 경로를 다시 재생해 보세요. BFS가 어떤 경로를 선택했는지, 어떤 간선이 병목이었는지, 총 유량이 어떻게 늘어났는지 확인할 수 있습니다.
• 세 개의 동기화된 행렬. 용량 행렬 C, 최종 유량 행렬 f, 잔여 행렬 C − f 사이를 전환해 보세요. 이 세 가지 지표는 플로우의 특성을 완벽하게 나타냅니다.
• 최소 컷 분할 뷰. S측과 T측 정점이 칩 형태로 나열되며, 교차하는 포화 간선은 빨간색으로 강조됩니다.
• 간선별 상세 테이블. 모든 간선에 대해 용량, 유량, 잔여량, 활용도 바 및 포화 표시를 제공합니다.
• 레이어 기반 좌우 레이아웃. 그래프는 소스로부터의 BFS 거리에 따라 그려지므로, 물이 왼쪽에서 오른쪽으로 흐르는 것처럼 시각화됩니다. 이는 교과서의 도식과 일치합니다.

입력 형식

1. 용량 포함 간선 리스트

한 줄에 간선 하나씩 입력합니다. 화살표 형식이 가장 읽기 좋지만 다음과 같은 대체 형식도 지원합니다.

또한 A, B, 10 · A B 10 · A -> B , 10 등도 허용됩니다. 동일한 쌍 사이의 여러 간선은 합산됩니다.

2. 용량 행렬

한 줄에 한 행씩, 공백이나 쉼표로 값을 구분하여 입력합니다. C[i][j] 값은 정점 i에서 정점 j로 가는 간선의 용량입니다. 간선이 없으면 0을 입력하세요. 행렬은 반드시 정사각형이어야 하며 대각선은 0이어야 합니다(셀프 루프 불가).

행렬 레이블 필드에 일치하는 정점 이름을 입력하세요(쉼표나 공백 구분). 생략 시 레이블은 기본적으로 S, A, B, …, T가 됩니다.

최대 유량의 응용 분야

실행 예시

"교과서" 빠른 예제는 소스 S와 싱크 T가 있는 6노드 네트워크를 나타냅니다. Edmonds-Karp를 실행하면 네 개의 증가 경로가 도출됩니다.

1. S → A → B → T, 병목 4 (간선 A-B가 제한 요소). 누적 유량: 4.
2. S → A → D → T, 병목 6. 누적 유량: 10.
3. S → C → D → T, 병목 4 (간선 D-T가 이제 제한 요소이며 4만 남음). 누적 유량: 14.
4. S → C → D → B → T, 병목 5. 누적 유량: 19.

더 이상 증가 경로가 없으므로 알고리즘이 중단됩니다. 최소 컷은 (S = {S, C}, T = {A, B, D, T})이며, 교차 간선은 S → A (용량 10)와 C → D (용량 9)로 그 합은 19입니다. 이는 최대 유량값과 정확히 일치합니다.

계산기 사용 방법

1. 탭을 사용하여 입력 형식을 선택하세요 (간선 리스트 권장 또는 용량 행렬).
2. 네트워크를 입력하세요. 빠른 예제에서 시작하여 수정할 수 있습니다. 행렬 입력의 경우 S, A, B, …, T 이외의 이름을 원하면 레이블도 함께 입력하세요.
3. 소스와 싱크를 지정하세요 (비워두면 S와 T를 자동으로 감지합니다).
4. 최대 유량 계산을 클릭하세요. 결과 페이지에 최대 유량값, 최소 컷 분할, 레이어드 그래프 시각화, 모든 증가 경로, 간선 활용도 테이블 및 세 개의 행렬(용량, 유량, 잔여량)이 표시됩니다.
5. 그래프 아래의 애니메이션을 재생하여 알고리즘의 결정을 확인하세요. 특정 증가 경로 단계를 클릭하여 해당 지점으로 바로 이동할 수도 있습니다.

제한 사항

• 정점 수: 최대 30개 — 시각화 및 행렬의 가독성을 유지하기 위함입니다.
• 간선 수: 최대 200개.
• 용량: 비음수, 최대 10⁹. 소수점 용량도 허용됩니다.
• 셀프 루프 불가: 표준 최대 유량 공식에서 셀프 루프는 유량을 전달하지 않으므로 제외됩니다.

자주 묻는 질문

최대 유량 문제란 무엇인가요?

각 간선이 비음수 용량을 갖는 유향 네트워크에서, 각 간선의 유량이 용량을 초과할 수 없고 소스와 싱크가 아닌 모든 정점으로 들어오는 유량이 나가는 유량과 같아야 한다는 규칙하에, 지정된 소스 정점 s에서 지정된 싱크 정점 t로 보낼 수 있는 유량의 최대치를 구하는 문제입니다. 이 답을 최대 유량값이라고 합니다.

Ford-Fulkerson 방법이란 무엇인가요?

Ford-Fulkerson은 최대 유량을 계산하기 위한 일반적인 기법입니다. 잔여 그래프에서 소스부터 싱크까지의 증가 경로를 반복적으로 찾고, 해당 경로를 따라 가능한 많은 유량(병목 용량)을 보낸 뒤 잔여 그래프를 업데이트합니다. 증가 경로가 더 이상 존재하지 않을 때 절차가 종료됩니다. 경로 선택을 위해 너비 우선 탐색(BFS)을 사용하면 Edmonds-Karp 알고리즘이라고 불리며, O(V · E²) 시간에 실행됩니다.

네트워크 플로우의 최소 컷이란 무엇인가요?

컷은 정점들을 소스가 포함된 집합 S와 싱크가 포함된 집합 T로 분할하는 것입니다. 컷의 용량은 S에서 T로 가는 간선들의 용량 합입니다. 최소 컷은 최소 용량을 갖는 컷을 말합니다. 유명한 최대 유량 최소 컷 정리는 최대 유량값이 항상 최소 컷 용량과 같음을 증명하므로, 하나를 찾으면 다른 하나도 자동으로 알 수 있습니다.

잔여 그래프란 무엇인가요?

잔여 그래프는 각 간선에 추가로 보낼 수 있는 유량이 얼마나 남았는지 추적합니다. 용량이 c이고 현재 유량이 f인 모든 원래 간선 (u, v)에 대해, 잔여 그래프는 용량이 c-f인 순방향 간선 (u, v)(남은 용량)와 용량이 f인 역방향 간선 (v, u)(취소 가능한 유량)를 포함합니다. 증가 경로는 잔여 그래프의 간선을 사용하여 알고리즘이 이전 결정을 취소할 수 있도록 합니다.

왜 이 도구는 증가 경로를 위해 BFS를 사용하나요?

너비 우선 탐색(Edmonds-Karp)으로 증가 경로를 선택하면 간선 용량에 관계없이 다항 시간 내에 종료가 보장됩니다. 임의의 경로 찾기 전략을 사용하는 기본 Ford-Fulkerson은 특정 입력에서 기하급수적인 횟수만큼 반복될 수 있으며, 무리수 용량의 경우 종료되지 않을 수도 있습니다. 또한 BFS는 읽고 이해하기 쉬운 최단 증가 경로를 생성합니다.

포화 간선은 무엇을 의미하나요?

간선의 유량이 용량과 같아서 더 이상 유량을 보낼 수 없을 때 해당 간선은 포화되었다고 합니다. 포화 간선은 네트워크의 병목 지점이며, 모든 최소 컷은 컷의 S쪽에서 T쪽으로 가는 포화 간선들로만 구성됩니다. 도구는 포화 간선을 빨간색으로 강조하여 병목 구조를 한눈에 볼 수 있게 합니다.

추가 정보

• 최대 유량 문제(Maximum flow problem) — Wikipedia
• Ford–Fulkerson 알고리즘 — Wikipedia
• Edmonds–Karp 알고리즘 — Wikipedia
• 최대 유량 최소 컷 정리(Max-flow min-cut theorem) — Wikipedia