Русская Википедия:Транзитивное сокращение
В математике транзитивным сокращением бинарного отношения R на множестве X называется минимальное отношение <math>R'</math> на X, такое, что транзитивное замыкание <math>R'</math> совпадает с транзитивным замыканием R. Если транзитивное замыкание R антисимметрично и конечно, то <math>R'</math> единственно. Однако ни существование, ни единственность в общем случае не гарантированы.
Пример
В теории графов любое бинарное отношение R на X можно понимать как ориентированный граф (V, A), где V = X — это вершины и A = R — дуги графа. Транзитивное сокращение графа иногда называют минимальным представлением. Следующие рисунки представляют нетранзитивное отношение (слева) и его транзитивное сокращение (справа).
Транзитивное сокращение конечного ориентированного ацикличного графа единственно.
Алгоритмы транзитивного сокращения
Транзитивное сокращение <math>R^-</math> отношения без циклов <math>R</math> можно найти используя его транзитивное замыкание <math>R^+</math>:
- <math>R^- = R - (R \circ R^+)</math>
Здесь <math>\circ</math> означает композицию отношений.
Ахо, Гарей и Ульман (1972), введшие в обиход термин «транзитивное сокращение» в описываемом здесь смысле, установили также связь между транзитивным замыканием и сокращением:
- для определения транзитивного сокращения они расширили нахождение транзитивного замыкания обработкой циклов;
- они показали, как из транзитивного сокращения получить транзитивное замыкание;
- они показали, что нахождение транзитивного сокращения и замыкания имеют одну и ту же вычислительную сложность.
Утилита tred в Graphviz[1] осуществляет транзитивное сокращение графа, используя поиск в глубину.
Расширяемые структура данных
Одной из самых хорошо изученных проблем в вычислительной теории графов является хранение последовательной истории транзитивных замыканий графа при вставке или удалении вершин и дуг. В 1987-м году Потре (J. A. La Poutré) и Жан ван Льювен (Jan van Leeuwen) описали в своем часто цитируемом труде Maintenance Of Transitive Closures And Transitive Reductions Of Graphs («Управление транзитивными замыканиями и сокращениями графа») алгоритм хранения истории как для замыкания, так и для сокращения графа.[2]
Алгоритм использует
- O(|Enew||V|)
время для последовательной вставки дуг и
- O(|Eold||V|+|Eold|2)
для последовательного удаления, где Eold — набор дуг перед вставкой или удалением и Enew — после. Для графов, в которых отсутствуют циклы, удаление требует только
- O(|Eold||V|)
времени.
См. также
Ссылки
Замечания
Ссылки
- Mathworld: Transitive reduction
- Э.Рейнгольд, Ю.Нивергельт, Н.Део КОМБИНАТОРНЫЕ АЛГОРИТМЫ. ТЕОРИЯ И ПРАКТИКА М.: Мир, 1980, 476 стр.
