Следует заметить, что этот новый штраф добавляется к предыдущей матрице весов, а не к первоначальной матрице С. Таким образом, штрафы равны р ( 1) р ( 7) 10, р ( 6) 5 и р ( г) О для всех остальных вершин. Соответствующий кратчайший остов изображен на рис. 10.12 ( в), и для него е 1, как и для предыдущего остова. Продолжая далее, штрафуем вершину 6 еще раз, полагая р ( 6) 5, и опять находим кратчайший остов. Результат показан на рис. 10.12 ( г), из которого видно, что теперь это гамильтонова цепь и, следовательно, по теореме 3 - кратчайшая гамильтонова цепь.
