Алгоритм Форда - Фалкерсона для нахождения потока наибольшей величины.

1°. Перенумеровать произвольным образом вершины сети , отличные от входа и выхода .

2°. Построить произвольный поток на транспортной сети (например, положить ).

3°. Просмотреть пути, соединяющие вход сети c выходом . Если поток полный, то перейти к пункту 4°. В противном случае рассмотреть путь , соединяющий с , все дуги которого не насыщены. Построить новый поток :

где . Повторить этот процесс до получения полного потока .

4°. Присвоить целочисленные метки вершинам сети и знаки «+» или «-» дугам по следующим правилам:

а) входу присвоить метку 0;

б) если вершина получила некоторую метку, а — еще непомеченная вершина, то вершине , такой что присвоить метку , а дуге— знак «+»; вершине , такой что , присвоить метку , а дуге— знак «-». Остальные непомеченные вершины и дуги метки и знака не получают;

в) повторить процесс, описанный в пункте 4°б) до тех пор, пока не прекратится появление новых отмеченных вершин и дуг. Если в результате процесса 4°б) вершина не получит метки, то поток обладает наибольшей величиной. В противном случае перейти к пункту 5°.

5°. Рассмотреть последовательность отмеченных вершин , каждая из которых имеет метку, равную номеру последующей вершины, и последовательность дуг и (не обязательно путь), соединяющих последовательные вершины из . Построить новый поток :

Перейти к пункту 4°.

2. Соотношение между величиной потока и пропускной способностью разреза сети.

Введем новые понятия теории транспортных сетей.

Определение 4: Пусть множество - такое множество вершин графа, что . Множество дуг, заходящих в , т. е. соединяющих вершины с вершинами, называется разрезом сети .