Следует заметить, что этот новый штраф добавляется к предыдущей матрице весов, а не к первоначальной ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Кристофайдс Н.N. Теория графов Алгоритмический подход


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

(cкачать страницу)

Смотреть книгу на libgen

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