2010년부터 · 매월 200만 회 이상의 도구 사용을 지원합니다
2010년부터
Chrome에 추가

내 도구함

자동 모드

저장된 도구가 없습니다.

프리미엄 버전으로 업그레이드하기
관련 도구
위상 정렬 계산기숫자 추출기
홈페이지 > 수학 관련 도구 > 고급 수학 연산 도구
 

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

용량 제약이 있는 방향 네트워크에서 포드-풀커슨과 에드먼즈-카프 알고리즘으로 소스에서 싱크까지의 최대 유량을 계산합니다. 모든 증가 경로를 애니메이션으로 보여주고 잔여 용량, 포화된 간선, 증명이 되는 최소 컷을 표시합니다.

무료로 사용가입 필요 없음즉시 결과 확인
네트워크 플로우 계산기 (최대 유량)지금 무료로 사용하기 ▼
빠른 예제:
교과서 (노드 6개) 작은 네트워크 클래식 CLRS 이분 그래프 스타일 행렬 입력
간선 형식: A -> B : 10 (화살표와 용량) 또는 A, B, 10.
행렬 형식: 한 줄에 한 행씩, C[i][j]는 간선 i → j의 용량입니다 (간선이 없으면 0 사용). 대각선은 0이어야 합니다.
쉼표나 공백으로 구분된 레이블을 행렬 행당 하나씩 입력하세요. 기본값은 S, A, B, …, T입니다.

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

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

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

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

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

용량 제한: 0 ≤ f(u, v) ≤ c(u, v) 모든 간선 (u, v)에 대해 유량 보존: Σ f(w, v) = Σ f(v, w) s, t를 제외한 모든 v ∈ V에 대해 유량값: |f| = Σ f(s, w) − Σ f(w, s) (s에서 나가는 순 유량)

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

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

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

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

while 잔여 그래프에 s에서 t로 가는 증가 경로 P가 존재하는 동안: b ← 경로 P에 있는 간선 (u, v)들의 최소 c_residual(u, v) 경로 P를 따라 b만큼 유량을 보냄 // 잔여량 및 유량 업데이트 return 총 유량 |f|

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

최대 유량 최소 컷 정리

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

cap(S, T) = Σ c(u, v) u ∈ S, v ∈ T 인 경우

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

최대 유량값 = 최소 컷 용량

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

학습을 위해 설계된 기능

입력 형식

1. 용량 포함 간선 리스트

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

S -> A : 10 S -> B : 13 A -> B : 10 B -> A : 4 B -> T : 14

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

2. 용량 행렬

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

S A B C D T S [ 0 10 0 10 0 0 ] A [ 0 0 4 2 8 0 ] B [ 0 0 0 0 0 10 ] C [ 0 0 0 0 9 0 ] D [ 0 0 6 0 0 10 ] T [ 0 0 0 0 0 0 ]

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

최대 유량의 응용 분야

분야최대 유량 활용 방식
운송 및 물류철도/도로/파이프라인 네트워크가 출발지에서 목적지까지 하루에 얼마나 많은 화물을 옮길 수 있는가?
이분 매칭작업자를 업무에, 학생을 프로젝트에 할당. 단위 용량 최대 유량을 통해 최대 매칭을 구함.
이미지 분할컴퓨터 비전의 Boykov–Kolmogorov 최소 컷을 통해 전경과 배경 픽셀을 분리.
네트워크 신뢰성최소 컷을 통해 끊어졌을 때 네트워크를 분단시키는 가장 취약한 연결 고리를 식별.
프로젝트 일정 계획폐쇄 문제 및 선택 문제를 최소 컷 문제로 변환하여 해결.
야구 탈락 결정특정 팀이 산술적으로 리그 우승에서 탈락했는지 여부를 결정.

실행 예시

"교과서" 빠른 예제는 소스 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. 그래프 아래의 애니메이션을 재생하여 알고리즘의 결정을 확인하세요. 특정 증가 경로 단계를 클릭하여 해당 지점으로 바로 이동할 수도 있습니다.

제한 사항

자주 묻는 질문

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

각 간선이 비음수 용량을 갖는 유향 네트워크에서, 각 간선의 유량이 용량을 초과할 수 없고 소스와 싱크가 아닌 모든 정점으로 들어오는 유량이 나가는 유량과 같아야 한다는 규칙하에, 지정된 소스 정점 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쪽으로 가는 포화 간선들로만 구성됩니다. 도구는 포화 간선을 빨간색으로 강조하여 병목 구조를 한눈에 볼 수 있게 합니다.

추가 정보

이 콘텐츠, 페이지 또는 도구를 다음과 같이 인용하세요:

"네트워크 플로우 계산기 (최대 유량)" - https://MiniWebtool.com/ko/네트워크-플로우-계산기-최대-유량/에서 MiniWebtool 인용, https://MiniWebtool.com/

miniwebtool 팀 제작. 업데이트: 2026년 4월 22일

또한 저희의 AI 수학 해결사 GPT를 사용하여 자연어 질문과 답변으로 수학 문제를 해결할 수 있습니다.

고급 수학 연산 도구:

인기·최신 도구:

최대 심박수 계산기1RM (1회 최대 반복) 계산기배관 유량 계산기모두 보기 →
홈페이지 > 수학 관련 도구 > 고급 수학 연산 도구 > 네트워크 플로우 계산기 (최대 유량)