Представьте жадный алгоритм, чтобы найти самый длинный цикл в невзвешенном графе

Question

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

Как найти самый длинный цикл используя жадный алгоритм?

Answer 1

"Самая длинная проблема простых циклов - это проблема нахождения цикла максимальной длины в графе. Как обобщение задачи о гамильтоновом цикле, она является NP-полной на общих графах и, фактически, на каждом классе графов, что Задача о гамильтоновом цикле является NP-полной. Самая длинная задача о простом цикле может быть решена за полиномиальное время на дополнениях к графам сравнимости. Она также может быть решена за полиномиальное время на любом классе графов с ограниченной шириной дерева или ограниченной кликой, такой как в качестве дистанционно-наследственных графов. Однако он NP-сложен даже в тех случаях, когда он ограничен расщепленными графами, круговыми графами или плоскими графами. В этой статье предлагается эвристический алгоритм, который может решить задачу за полиномиальное время. Для решения самого простого простого Задача цикла с использованием матрицы смежности и списка смежности путем создания дерева данной задачи, чтобы найти самый длинный простой цикл в качестве самого глубокого пути в дереве, после чего повторно соединить конечный узел самого глубокого пути с узлом root. Это открытый вопрос о сложности задачи на простых невзвешенных графах. Алгоритм реализован на простом помеченном графе без параллельных ребер и без selfl oop. Наихудшая временная сложность для предложенного алгоритма - O (V + E).

Алгоритм самого длинного простого цикла. В предлагаемом алгоритме входной граф считается простым графом (т. Е. Без self-l * 1032). * и без параллельных ребер) алгоритм для Longest Simple Cycle в простом графе приведен ниже:

1. Перечислите все узлы, чтобы вычислить степень каждого узла, чтобы найти узел с наивысшей степенью.

2. Назначить узел с наивысшей степенью в качестве root для дерева.

3. Построить дерево T данного графа G, учитывая соседние узлы как преемники и предшественники соответственно для каждой вершины, использующей матрицу смежности.

4. Применяйте предложенный алгоритм LS C, чтобы найти самый длинный путь.

5. Соедините конечный узел самого длинного пути с помощью root и получите путь, считая его самым длинным циклом в графе. "

Heuristi c Алгоритм для L Задача ongest Simple Cycle