Коллеги - как из первой картинки получить эту самую permutation 4,3,5,1,2?
2 2012-07-25 17:11:31
Тема: Поиск максимального простого пути (0 ответов, оставленных в Problems)
Имеется неориентированный невзвешенный граф с циклами (вершин ~ 8000, ребер ~ 80000). Задача - найти максимальный простой путь между любыми двумя вершинами (т.е. вершины не должны повторяться). Понятно, что NP-complete, вопрос как максимально эффективно осуществить перебор? Может быть можно быстро вычислить приблизительное значение? Пробовал dijkstra c весом -1 получил путь 6400 вершин, хочется лучше 
Заранее спасибо!
3 2012-06-07 19:31:28
Re: Каким аглоритмом можно произвести декомпозицию сильно связанного графа (6 ответов, оставленных в Algo)
Есть подозрения, что точки артикуляции в орграфе это не то же самое, что в неориентированном. В данном документе используются некие доминаторы:
http://www.sofsem.cz/sofsem12/files/pre … aliano.pdf
Гуру могут прокоментировать?
4 2012-05-01 20:12:29
Re: Каким аглоритмом можно произвести декомпозицию сильно связанного графа (6 ответов, оставленных в Algo)
Спасибо за разъяснения. Нашел реализацию на java - буду портировать на python
5 2012-05-01 00:53:06
Re: Каким аглоритмом можно произвести декомпозицию сильно связанного графа (6 ответов, оставленных в Algo)
Вроде, получается, спасибо. А как теперь получить подграфы, на которые разбивается основной граф?
6 2012-04-30 14:22:00
Тема: Каким аглоритмом можно произвести декомпозицию сильно связанного графа (6 ответов, оставленных в Algo)
Есть следующий сильно связанный граф:
Хотелось бы как-то разбить его на 3 сильно связанных подграфа и получить их структуру.
Спасибо!
7 2011-10-08 13:44:38
Re: Алгоритм поиска Гамильтонова пути на неориентированом графе (3 ответов, оставленных в Algo)
http://www.dharwadker.org/hamilton/ это не то же?