2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 нахождение гамильтоновой цепи мин-й длины (алгоритм Литтла)
Сообщение11.06.2007, 10:52 
помогите разобраться пожалуйста, препод говорит, что чтобы применить алгоритм Литтла нужно сначала сделать какие то преобразования с графом
пытался найти материал в интернете и учебниках, но там такого нет
сам алгоритм Литтла я понимаю, но как его применить для цепи, не знаю

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

 
 
 
 
Сообщение11.06.2007, 11:22 
Аватара пользователя
Вот этот пример: http://rain.ifmo.ru/cat/view.php/theory ... pprox-2004 (пример 1) пойдет?

 
 
 
 
Сообщение11.06.2007, 11:43 
нет, к сожалению это нахождение гамильтонова цикла, а мне нужно именно гамильтонова цепь

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

 
 
 
 
Сообщение12.06.2007, 16:57 
Jack писал(а):
нет, к сожалению это нахождение гамильтонова цикла, а мне нужно именно гамильтонова цепь
Гамильтонова цепь отличается от гамильтонова цикла тем, что определена на неориентированном графе. Возможно преобразование, о котором говорил Ваш преподаватель - это преобразование неориентированного графа в ориентированный. Попробуйте заменить в исходном графе каждое ребро A-B на пару дуг A->B и B->A.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group