Как удалить циклы в невзвешенном ориентированном графе, так чтобы количество ребер было максимальным?
Пусть 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 'может иметь одинаковую начальную или одну и ту же конечную вершину. Это противоречит некоторым определениям направленных остовных деревьев, используемым в литературе .
РЕДАКТИРОВАТЬ: Добавлено интуитивно понятное описание, справочная информация и примечания, относящиеся к остовным деревьям.