Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

9:07p

Есть невзвешенный орграф.
Хочется найти его максимальный ациклический подграф (разумеется, содержащий все вершины исходного). Проблема в том, что я не могу придумать нормальное определение, по какому именно критерию он должен быть максимальным. Хочется сказать, что по включению, но таких может быть несколько и со здравым смыслом согласуются не все из них. Максимальный по количеству ребер - чем-то мне этот критерий просто не нравится :)
Есть вариант построить любое дерево поиска в ширину/глубину, а потом дописать к нему все ребра, не приводящие к появлению цикла, но это тоже не катит - таких наборов ребер, опять же, может быть несколько и множество этих наборов не является вполне упорядоченным по включению.