Пусть G - невзвешенный ориентированный граф, содержащий циклы. Я ищу алгоритм, который находит/создает все ациклические графы G ', состоящие из всех вершин из G и подмножества ребер G, достаточно малые, чтобы G' ациклично.
Более формальный: искомый алгоритм потребляет G и создает набор ациклических графов S, где каждый граф G 'в S удовлетворяет следующим свойствам:
- G 'содержит все вершины из G.
- G 'содержит подмножество ребер G, такое, что G' ациклично.
- Число ребер G 'максимизировано. Это означает, что G '' не удовлетворяет свойствам 1 и 2, так что G '' содержит больше ребер, тогда G 'и G' 'ацикличны.
Фон: исходный граф G моделирует парное упорядочение между элементами. Это не может быть использовано как упорядочение по всем элементам из-за циклов на графике. Поэтому максимальные ациклические графы G должны моделировать наилучшее возможное приближение к этому упорядочению, пытаясь как можно более эффективно учитывать парное упорядочивающее отношение.
В наивном подходе можно было удалить все возможные комбинации ребер и проверить ацикличность после каждого удаления. В этом случае существует сильно разветвляющееся дерево вариаций, означающее плохое время и сложность пространства.
Примечание. Проблема может быть связана с остовным деревом, и вы можете определить графы G как своего рода ориентированное остовное дерево. Но имейте в виду, что в моем случае пара ребер в G 'может иметь один и тот же начальный или один и тот же конечный вершин. Это противоречит некоторым определениям ориентированных связующих деревьев, используемых в литературе.
EDIT: добавлено интуитивное описание, справочная информация и примечание, связанные с перекрытием деревьев.
