Задача поиска контура минимальной средней длины

1. Определяем произвольный контур.

Затем определяем контур отрицательной длины, повторяем шаг 1, и т.д. до тех пор, пока на очередном шаге таких контуров не найдется.

Так как на каждом шаге длины всех дуг изменялись на одно и то же число, то на последнем шаге длина каждой дуги равна lij - h, где h - суммарное изменение длины каждой дуги на всех шагах.

Значение h равно минимальной средней длине дуг контуров графа. При этом контуром минимальной средней длины является контур, определенный на предпоследнем шаге.