Можно ли создать обратно DAG из всех возможных топологических сортировок?

Question

Можно ли создать исходный DAG из всех возможных топологических типов DAG? А что если какое-то число n (меньше, чем все возможные топологические виды) заданных топологических сортов, может ли DAG быть сконструирован таким образом, чтобы он удовлетворял данным n топологическим порядкам?

Answer 1

Учитывая вершины вашей DAG, создайте новое отношение a->b, определяемое a->b тогда и только тогда, когда a появляется перед b во всех заданных топологических сортировках.

Этот новый граф является ацикличным c, транзитивным и совместимым с данными топологическими сортами.

Даже при всех топологических упорядочениях невозможно однозначно определить DAG, поскольку следующие два трехвершинных DAG имеют одинаковые топологические упорядочения .

a -> b -> c

a -> b -> c
 \________^

Однако описанная выше процедура приводит к транзитивному замыканию исходного DAG, если вы получили все возможные топологические упорядочения. Потому что если в исходном DAG есть путь от a до b, то обязательно a появляется перед b в каждом топологическом порядке. И наоборот, если a появляется перед b в каждом топологическом порядке, то должен быть путь между a и b в исходном DAG. Если нет, добавьте ребро между b и a в исходной группе обеспечения доступности баз данных (это не может образовать цикл, поскольку пути от a до b нет), и топологически сортируйте группу обеспечения доступности баз данных. Это дает действительный топологический вид исходного DAG, где b обязательно появляется перед a, что дает противоречие.