Условие задачи
Требуется определить максимальный поток в сети, приведенной на рисунке 1, из вершины Xi в вершину Xj, где числа на дугах, снабженные стрелками, означают пропускные способности этих дуг в указанных направлениях. Номера вершин i и j для каждого варианта приведены в таблице.
Ответ
Придадим вершине 5 оценку 0.
Вычислим оценки для остальных вершин:
8: 0+1=1
6: 1+4=5
4: ...