является ли однонаправленный граф, построенный из двунаправленного графа, DAG?

Question

Для приведенного выше графика.

for every vertex:
   remove back edge from children to it.

Возможно, это всегда приведет к DAG, но я не могу доказать это. есть ли доказательства этому или кто-то может предоставить встречный аргумент?

Answer 1

Пусть S будет набором обработанных узлов.

Гипотеза

• S не имеет цикла.
• Любой узел S имеет нет задника от детей.

Инициализация:

Добавьте 1 к S.

• 1 не имеет отступа в соответствии с вашим alg
• это не цикл (не l oop сам по себе, поскольку нет отступа)

Повторение:

• Нет цикла:

Пусть t будет следующим добавляемым узлом. S ациклично c по гипотезе Чтобы получить цикл в S U {t}, нам нужно t, чтобы быть в цикле.

Но t не может иметь ребра ни для какого узла n из S. Потому что, если это так, существует ссылка от n до t (график изначально не направлен), что означает, что t является потомком n. По вашему алгоритму, когда n был добавлен к S, задний край из t был удален.

Поскольку нет никакого ребра от t до любого узла в S, существует нет цикла, включающего t в S U {t}.

Так что S U { t } все еще является ациклическим c.

• Нет отступа:

Все узлы в S в порядке гипотезы.

При добавлении t дочерние элементы t удаляют ребро заднего края (до t).

Так что S U {t} все еще в порядке