유량 또는 매칭 질의를 실행하는 방법 01 네트워크를 구성합니다. Flow network S→T 프리셋은 6개 노드의 유향 네트워크입니다. 이분 그래프 판정은 Bipartite K₃,₃ 프리셋과 임의의 격자도 받습니다. 02 Dinic max-flow 또는 Edmonds–Karp를 선택 하고 Source S와 Sink T를 설정한 뒤 최대 유량, 최소 컷 용량, 교차 확인 행, 간선별 유량/용량 표를 읽습니다. 03 Bipartite check 에서는 판정, 왼쪽과 오른쪽 집합, 그리고 답이 No일 때 홀수 사이클 증거를 읽습니다. 04 Hungarian matching 에서는 이분 그래프를 불러와 매칭 크기, 쌍, 최소 정점 덮개, 매칭되지 않은 정점을 읽습니다. 05 실행을 단계별로 진행 하며 증가 경로가 유량 값을 올리는 모습을 확인합니다.
계산 예시
설정
계산 결과
유량 프리셋, Dinic S → T
최대 유량 19 , 최소 컷 용량 19 , 교차 확인(Edmonds–Karp) 19 , 컷 간선 S→A, B→D , 소스 쪽 S, B
유량 프리셋, 간선별 유량
S→A 10/10 , S→B 9/10 , A→C 4/4 , A→D 6/8 , B→D 9/9 , C→T 9/10 , D→C 5/6 , D→T 10/10
Bipartite K₃,₃, Hungarian matching
최대 매칭 3 , 쌍 L1–R3, L2–R2, L3–R1 , 최소 정점 덮개 L1, L2, L3 , 미매칭 —
Cycle C₅, Bipartite check
이분 그래프 No , 홀수 사이클 증거 C → B → A → E → D → C
Grid 4 × 5, Bipartite check
이분 그래프 Yes , 왼쪽 10 개 노드(1-1, 1-3, 1-5, 2-2부터), 오른쪽 10 개(1-2, 1-4, 2-1부터)
두 유량 알고리즘은 19 에서 일치하고, 컷 간선이 상한을 뒷받침합니다. S→A가 10 , B→D가 9 를 실어 합이 최대 유량입니다. 싱크는 C→T로 9 , D→T로 10 을 받아 다시 19 입니다.
왜 컷이 유량을 증명하는가 최대 유량 최소 컷은 최선의 유량이 가장 저렴한 병목과 같다고 말합니다. Dinic은 증가 경로가 남지 않으면 멈추고, 패널은 그때 S에서 아직 도달 가능한 노드 — 소스 쪽 S, B — 와 그것을 떠나는 간선 S→A 와 B→D 를 보여 줍니다. 그 용량 10 과 9 를 더하면 유량이 됩니다. 모든 단위가 이 컷을 지나야 하므로 더 큰 유량은 존재하지 않습니다. 매칭 쪽에서는 Kőnig의 정리가 같은 형식의 증명을 줍니다. 크기 3 의 매칭과 크기 3 의 정점 덮개가 서로를 고정합니다.
한계
매칭에는 이분 그래프가 필요합니다. Petersen 프리셋에서 Hungarian matching을 실행하면 패널은 부분 답을 반환하는 대신 "Graph is not bipartite (odd cycle O3 → O2 → O1 → O5 → O4 → O3) — the Hungarian/Kuhn algorithm does not apply"라며 거부합니다. 일반 그래프 매칭은 제공되지 않습니다.
한 번에 하나의 소스-싱크 쌍, 비용 없음. min-cost flow, 다품종 유량, 간선 하한은 없습니다. 쌍을 차례로 실행하고 소스 쪽을 비교하세요. 하지 않는 것. 보고된 최소 컷을 넘어 컷을 열거하지 않고 네트워크 파일도 가져오지 않습니다. 네트워크를 캔버스에서 구성하고 인접 행렬을 math tools 로 가져가 추가 대수를 하거나 Components 로 도달 가능성을 나열하세요.
방향 함정 컷 간선은 유향 쌍으로 출력됩니다. 유향 Flow 프리셋에서는 S→A 와 B→D 입니다. 무방향 기본 그래프에서는 Dinic A→F가 A→B, A→C 를 소스 쪽 A 로 출력합니다. 소스 쪽은 실행 전반에서 안정적인 판독값 — 알고리즘이 멈출 때 S에서 아직 도달 가능한 모든 것 — 이므로, 손으로 컷을 재확인할 때는 화살표 방향이 아니라 그 행을 비교하세요.
활용 사례 용량 계획 유량 프리셋은 19 단위 수요 중 얼마나 통과할 수 있는지와 병목이 어디인지 보여 줍니다. S→B는 1 단위 여유를 유지하고 A→D는 2 를 남기지만, 컷 S→A / B→D는 포화 상태입니다. 컷 간선의 용량을 올리면 유량 값이 움직이고, 네트워크 내부 간선을 올리면 보통 움직이지 않습니다.
할당 문제 Bipartite K₃,₃에서 Hungarian 패널은 왼쪽 노드 세 개를 모두 짝지어 같은 크기의 덮개를 출력하므로 할당이 증명 가능하게 최대입니다. 격자는 이분 그래프 판정에 Yes라고 답하며 10/10으로 똑같이 나뉘고, C₅는 No라고 답하며 홀수 사이클을 돌려줍니다 — 2색 칠이 존재하지 않는다는 증명서입니다. 그런 다음 Traversal 패널이 색 그룹을 노드별로 보여 줄 수 있습니다.
개인정보 모든 유량, 색칠, 매칭 계산은 브라우저에서 실행되며 아무것도 업로드되지 않습니다.
참고 문헌
Wikipedia, Maximum flow problem , en.wikipedia.org (访问日期:2026-10-07)— 증가 경로와 유량 값.
Wikipedia, Max-flow min-cut theorem , en.wikipedia.org (访问日期:2026-10-07)— 유량과 컷 용량의 일치.
Wikipedia, Bipartite graph , en.wikipedia.org (访问日期:2026-10-07)— 2색 칠과 홀수 사이클.
Wikipedia, Maximum cardinality matching , en.wikipedia.org (访问日期:2026-10-07)— 증가 경로 기반 매칭.
Wikipedia, Kőnig's theorem (graph theory) , en.wikipedia.org (访问日期:2026-10-07)— 이분 그래프에서 매칭과 정점 덮개의 일치.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07