최대 유량·최소 컷 계산기: 잔여 네트워크 최대유량
최대 유량·최소 컷 계산기 사용법
- 입력 항목은 유향 간선: 출발 도착 용량·노드 수·출발 노드·도착 노드입니다.
- 유향 간선의 용량을 같은 단위로 입력하고 서로 다른 출발·도착 노드를 지정합니다. 중간 노드에서 유입량과 유출량이 같다고 가정합니다.
- 계산하기를 누르면 최대 유량·최소 컷 출발측 노드 결과를 확인할 수 있습니다. 아래 고정 예시와 비교할 때는 입력 조건도 같아야 합니다.
| 입력 항목 | 예시 값 | 입력 안내 |
|---|---|---|
| 유향 간선: 출발 도착 용량 | 1 2 3 1 3 2 2 3 1 2 4 2 3 4 3 | 한 행씩 줄바꿈, 열은 공백 또는 쉼표로 구분합니다. 표 안에서는 천 단위 쉼표를 쓰지 마세요. |
| 노드 수 | 4 | 2~50 정수 · 천 단위 쉼표 사용 가능 |
| 출발 노드 | 1 | 1~50 정수 · 천 단위 쉼표 사용 가능 |
| 도착 노드 | 4 | 1~50 정수 · 천 단위 쉼표 사용 가능 |
| 결과 항목 | 예시 결과 |
|---|---|
| 최대 유량 | 5 |
| 최소 컷 출발측 노드 | 1 |
| 컷 출발 | 컷 도착 | 용량 |
|---|---|---|
| 1 | 2 | 3 |
| 1 | 3 | 2 |
위 표는 고정된 예시입니다. 직접 입력한 값의 결과는 입력란 아래에 표시됩니다. 실제 이용 시에는 아래 계산 방법과 적용 조건을 함께 확인하세요.
계산 방법
입력 자료를 다음 방식으로 계산합니다. 잔여 네트워크 최대유량
알아두세요
Edmonds–Karp 잔여 네트워크 알고리즘입니다. 비음수 유한 용량을 입력하세요. 입력 범위 안의 모형 계산이며 실제 자료의 가정 충족 여부를 자동 판정하지 않습니다.
자주 묻는 질문
최소 컷의 용량이 최대 유량과 같은 이유는 무엇인가요?
출발점과 도착점을 분리하는 경계의 용량은 통과 가능한 유량의 상한입니다. 최대유량 계산이 완료되면 그 상한과 일치하는 최소 컷을 함께 확인할 수 있습니다.
계산 방식 참고: SciPy 최적화 방법 목록 — 관련 계산 원리 참고
입력·결과 안내 점검: · 생활 계산기