1
Алгоритм сильно связанных компонентов Тарьяна может найти только фундаментальные циклы или все циклы, которые находятся на графике?Найти все циклы в ориентированном графе?
A
ответ
0
Он не может найти все циклы, пока он работает в O (V + E) (полиномиальное время). Если бы это было возможно, это могло бы решить проблему гамильтонова цикла в полиномиальное время, но эта проблема NP-жесткая.
+0
Идея ответа правильная, но неточная. Дело в том, что мы не знаем, могут ли NP-Hard проблемы решаться полиномиально. Обратите внимание, однако, что эта проблема намного сложнее, и даже если P = NP не может быть решена полиномиально, так как размер вывода экспоненциальный во входе (может быть экспоненциальным числом циклов). – amit
Смежные вопросы
- 1. Циклы снятия в взвешенном ориентированном графе
- 2. Найти все вершины в цикле в ориентированном графе
- 3. Циклы в ориентированном графике
- 4. Вычисление числа простого пути в ориентированном графе, содержащем циклы
- 5. Алгоритм поиска кратчайших циклов в ориентированном графе
- 6. Как найти вероятность пути в ориентированном графе?
- 7. Swi пролог найти все соседи кивнув в ориентированном графе
- 8. Найти все ребра между любыми двумя вершинами в ориентированном графе
- 9. Поиск всех циклов в ориентированном графе
- 10. Найти цикл наименьшей длины в ориентированном графе с положительными весами
- 11. найти список всех узлов в ориентированном графе
- 12. Список всех отрицательных циклов в ориентированном графе
- 13. Избегание циклов в ориентированном графе
- 14. Найти общий путь среди всех возможных путей в ориентированном графе
- 15. Будет ли DFS из каждого узла давать все циклы в ориентированном графе
- 16. Эффективный поиск в ориентированном графе
- 17. Найти все пути из источника в пункт назначения в взвешенном циклическом ориентированном графе
- 18. Обнаружение циклов mulitple в циклическом ориентированном графе
- 19. Моделирование сети в ориентированном графе
- 20. Сколько компонентов в ориентированном графе?
- 21. Посетите все узлы ровно один раз в ориентированном графе
- 22. Python igraph: получить все возможные пути в ориентированном графе
- 23. Найти все пути с циклами в ориентированном графе, учитывая исходную вершину
- 24. Найти отрицательный цикл в ориентированном графе, используя Dijkstra?
- 25. Лучший способ найти, существует ли путь в однонаправленном ориентированном графе
- 26. Поиск всех корней в ориентированном графе
- 27. Найти все циклы в направленном и неориентированном графике
- 28. Подсчитайте количество Эйлеровских PATH в ориентированном графе?
- 29. Серия ациклического путь в ориентированном графе невзвешенного
- 30. Максимальный путь вес в ориентированном графе
Можете ли вы рассказать нам, для чего вам это нужно? Я не могу представить какую-либо актуальную проблему, когда это было бы полезным подходом. – pentadecagon
Мне нужно найти все циклы на графике. Алгоритм Тарьяна не указан в следующем пункте: он находит все циклы или только основные циклы на графике. –