нахождение гамильтоновой цепи мин-й длины (алгоритм Литтла)

[Jack]

помогите разобраться пожалуйста, препод говорит, что чтобы применить алгоритм Литтла нужно сначала сделать какие то преобразования с графом
пытался найти материал в интернете и учебниках, но там такого нет
сам алгоритм Литтла я понимаю, но как его применить для цепи, не знаю

Заранее большое спасибо.

[Brukvalub]

Вот этот пример: http://rain.ifmo.ru/cat/view.php/theory ... pprox-2004 (пример 1) пойдет?

[Jack]

нет, к сожалению это нахождение гамильтонова цикла, а мне нужно именно гамильтонова цепь

[Jack]

вопрос актуален еще день
помогите пожалуйста подруге, у нее завтра зачет
спасибо!

[Yuri Gendelman]

Jack писал(а):

нет, к сожалению это нахождение гамильтонова цикла, а мне нужно именно гамильтонова цепь

Гамильтонова цепь отличается от гамильтонова цикла тем, что определена на неориентированном графе. Возможно преобразование, о котором говорил Ваш преподаватель - это преобразование неориентированного графа в ориентированный. Попробуйте заменить в исходном графе каждое ребро A-B на пару дуг A->B и B->A.