418
правок
Изменения
→Алгоритм для антисимметричных отношений
Пусть <tex> (k, m) \in E' </tex>. Тогда <tex> k \neq m </tex> (иначе после удаления ребра <tex> (k, m) </tex> из <tex> E' </tex> получится меньший граф с тем же транзитивным замыканием, что противоречит определению). Поэтому в пути от <tex> k </tex> к <tex> m </tex> в графе <tex> G </tex> есть как минимум одно ребро.
Возьмём <tex> l </tex> такую, что <tex> l </tex> достижима из <tex> k </tex>, и есть ребро из <tex> l </tex> в <tex> m </tex>. Предположим, что <tex> k \neq l </tex>. Так как граф ацикличен, <tex> l \neq m </tex>. Так же так как транзитивное замыкание <tex> G </tex> равно транзитивному замыканию <tex> G' </tex>, в графе <tex> G' </tex> вершина <tex> l </tex> достижима из <tex> k </tex>, а <tex> m </tex> — из <tex> l </tex>. <tex> G' </tex> также ацикличен, поэтому в пути от <tex> k </tex> к <tex> l </tex> не может быть ребра <tex> (k, m) </tex>. Также в пути от <tex> l </tex> к <tex> m </tex> не может быть ребра <tex> (k, m) </tex>. Поэтому существует путь в <tex> G' </tex> от <tex> k </tex> к <tex> m </tex>, который не содержит ребро <tex> (k, m) </tex>. Поэтому удаление ребра не изменяет транзитивное замыкание.
Теперь предположим, что <tex> (k, m) \notin in E' </tex>. Так как <tex> G </tex> ацикличен, <tex> k \neq m </tex> и отсюда в <tex> G' </tex> вершина <tex> m </tex> достижима из <tex> k </tex>. Поскольку <tex> (k, m) \notin E' </tex>, существует вершина <tex> l </tex> такая, что есть путь из <tex> k </tex> в <tex> l </tex> и из <tex> l </tex> в <tex> m </tex>, и <tex> k \neq l \neq m </tex>. Это значит, что в <tex> G </tex> что есть путь из <tex> k </tex> в <tex> l </tex> и из <tex> l </tex> в <tex> m </tex> (причём в каждом пути будет как минимум по одному ребру). Поскольку <tex> G </tex> ацикличен, это значит, что в <tex> G </tex> существует вершина <tex> l' </tex> такая, что есть путь как минимум в одно ребро из <tex> k </tex> в <tex> l' </tex> и есть ребро <tex> (l', m) </tex>. Это противоречит нашему предположению.
}}
