Кратчайшая гамильтонова цепь

Найдем кратчайший остов графа , такой что . Это и будет кратчайшая гамильтонова цепь. (задача а).

Суть алгоритма решения состоит в решении задачи построения SST и затем в использовании дерева решений.

Решение же задачи об отыскании кратчайшей гамильтоновой цепи с заданными коньцевыми вершинами и сведем к предыдущей задаче используя теорему.

Теорема 4.2. Пусть – матрица реберных весов графа и – достаточно большое положительное число, большее веса любой гамильтоновой цепи. Тогда решение задачи а) с матрицей весов , где является решением задачи б) с первоначальной матрицей.

является решение задачи б) с первоначальной матрицей весов.