다음 조건을 만족하는 유향 가중치 그래프를 유량 그래프라고 한다.
1. 어떤 특별한 점 s,d가 있어 s와 d의 supernode(s와 d의 진입/진출 간선을 한 점으로 모은 것)과 다른 모든 정점은 진입가중치 합과 진출 가중치 합이 같다.
2. s는 진출간선만, d는 진입간선만 있다.
유량 그래프의 모든 가중치가 0 이상인 간선에 대해 간선의 가중치보다 큰 가중치를 가지는 간선으로 이루어진 그래프(무향을 포함한다)를 유로 그래프라고 한다.
유로 그래프와 유량 그래프는 다대다 대응이 된다.
유량 그래프의 s의 진출 가중치 합 (d의 진입 가중치 합)을 유량 그래프의 유량이라 한다.
최대 유량 그래프란 어떤 유로 그래프에 대해 유량 그래프의 유량이 최대가 될 때 그 그래프를 최대 유량 그래프라고 하고, 그 때의 유량을 최대 유량이라 한다.
어떤 정점에서 다른 정점으로 왕복할 수 없을 때 두 정점은 분할되었다고 한다. (단방향 이동은 가능할 수 있음)
컷이란 어떤 가중치 있는 그래프의 정점을 두 부분으로 분할했을 때 두 부분에 모두 걸쳐있는 간선의 가중치 합을 컷이라 한다.
어떤 그래프의 컷의 최대가 되게 하는 분할을 최대 컷 분할이라 하고 그 때의 컷을 최대 컷이라 한다.
최대 유량 최소 컷 정리란, 어떤 유로 그래프의 최대 유량은 s노드와 d 노드를 다른 부분으로 분할하는 최대 컷과 같다는 정리이다.
최소 컷 자체는 구하기 대단히 힘들지만, 최대 유량은 상대적으로 구하기 쉽기 때문에 최소 컷을 구하기 위해 최대 유량을 이용한다.
