Пусть G - невзвешенный ориентированный граф, содержащий циклы.Я ищу алгоритм, который находит / создает все ациклические графы G ', состоящие из всех вершин в G и подмножества ребер G, достаточно малых, чтобы сделать G' ациклическим.
Более формально:требуемый алгоритм использует G и создает набор ациклических графов S, где каждый граф G 'в S удовлетворяет следующим свойствам:
- G' содержит все вершины G.
- G 'содержитподмножество ребер G, такое, что G 'ациклично.
- Число ребер G' максимизировано.Это означает: не существует G '', удовлетворяющего свойствам 1 и 2, так что G '' содержит больше ребер, чем G ', а G' 'ациклично.
Справочная информация: Исходный граф G моделируетпопарное упорядочение между элементами.Это не может быть использовано как упорядочение по всем элементам из-за циклов в графе.Таким образом, максимальные ациклические графы G 'должны моделировать максимально возможное приближение к этому упорядочению, стараясь максимально учитывать отношение парного упорядочения.
В наивном подходе можно удалить все возможные комбинации ребери проверять ацикличность после каждого удаления.В этом случае существует сильно разветвленное дерево вариаций, означающее плохую сложность времени и пространства.
Примечание. Проблема может быть связана с остовным деревом, и вы можете определить графы G как вид * 1017.* направлено остовное дерево.Но имейте в виду, что в моем сценарии пара ребер в G 'может иметь одинаковую начальную или одинаковую конечную вершину.Это противоречит некоторым определениям направленных остовных деревьев, используемым в литературе .
РЕДАКТИРОВАТЬ: Добавлено интуитивно понятное описание, справочная информация и примечания, относящиеся к остовным деревьям.