2014 dxdy logo

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

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




 
 Алгоритм поиска самой длинной цепи в неориентированном графе
Сообщение06.05.2019, 04:46 
Дан неориентированный граф с длинами рёбер. Требуется найти (за приемлемое время) в нём самую длинную цепочку.
Граф небольшой (~10 вершин), однако мне кажется, что здесь не подойдёт алгоритм перебора.
С другой стороны, я думаю, что такой алгоритм, как выбор самого длинного ребра и присоединение к сформировавшейся цепочке самого длинного ребра с одного из концов, пока это возможно, а также такой алгоритм, как выкидывание самого короткого ребра (если не нарушается связность) до тех пор, пока граф не станет эйлеровым (0-2 вершины нечётной степени) являются приближёнными, а не точными.

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

 
 
 
 Re: Алгоритм поиска самой длинной цепи в неориентированном графе
Сообщение06.05.2019, 07:23 
В принципе, эту задачу можно свести к задаче о поиске самой длинной цепочки в обычном графе (т.к. ребро с длиной можно заменить на необходимое количество единичных рёбер), а она NP-трудная, значит решается перебором.

 
 
 
 Re: Алгоритм поиска самой длинной цепи в неориентированном графе
Сообщение06.05.2019, 09:53 
Для каждого подмножества вершин и каждой вершины из этого подмножества найдите длиннейшую цепочку начинающуюся в этой вершине.

 
 
 
 Re: Алгоритм поиска самой длинной цепи в неориентированном графе
Сообщение06.05.2019, 10:16 
Null в сообщении #1391285 писал(а):
Для каждого подмножества вершин и каждой вершины из этого подмножества найдите длиннейшую цепочку начинающуюся в этой вершине.

Наверное, не помешает уточнить:
Для каждого подмножества вершин и каждой вершины из этого подмножества найдите длиннейшую цепочку, начинающуюся в этой вершине, целиком лежащую в этом подмножестве.

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


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