2014 dxdy logo

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

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




 
 Обобщение понятия гамильтонова графа
Сообщение30.07.2014, 21:17 
Мне тут на досуге подумалось: а что если обобщить понятие гамильтонова пути и, соответственно, гамильтонова графа следующим образом: называть $k$-гамильтоновым граф в котором существует путь, позволяющий обойти все вершины графа, посетив каждую не более $k$ раз.
Если ввести такое понятие, то, может быть, возможно научится каким-то образом вычислять верхнюю оценку степени гамильтоновости графа, если известна такая оценка для отдельных его частей, можно как-то связывать $k$-гамильтоновость с приведением к графу с меньшей степенью гамильтоновости с помощью стягивания вершин или удаления рёбер...
Возможно, для достаточно больших, $k$ (например для $k=O(\log{n})$ или $k=O(\sqrt{n})$) возможен полиномиальный алгоритм проверки на k-гамильтоновость?
Кто что думает по этому поводу? Может быть, кто-то знает книги, в которых уже описаны рассуждения в этом русле, и я просто изобретаю велосипед?

 
 
 
 Re: Обобщение понятия гамильтонова графа
Сообщение30.07.2014, 23:26 
У меня такой вопрос. Если граф 1-гамильтонов как вы определили. То он в то же время и 2-гамильтонов, 3-гамильтонов итд. Я правильно трактую вашу идею?

 
 
 
 Re: Обобщение понятия гамильтонова графа
Сообщение31.07.2014, 00:25 
Ну, это уже издержки формализации (хотя штука, конечно, важная). Да, я сформулировал именно так.

 
 
 
 Re: Обобщение понятия гамильтонова графа
Сообщение01.08.2014, 11:20 
fractalon в сообщении #891970 писал(а):
Ну, это уже издержки формализации (хотя штука, конечно, важная).

Разумеется, формализация штука плодотворная. :-) А что вам мешает наложить оганичение на кратность посещения вершин, как то связав ограничение с $k$. С уважением,

 
 
 
 Re: Обобщение понятия гамильтонова графа
Сообщение02.08.2014, 04:50 
Кратность - то есть каждая вершина должна быть посещена $nk$ раз, где $n>1$ - целое? Интересно, надо подумать...
Формулировку конечно можно изменить, сказав, что не существует пути, обходящего все вершины и посещающего каждую не более $k-1$ раз.

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


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