Введение
Наименьшее транзитивное отношение, содержащее данное бинарное отношение
транзитивное замыкание бинарного отношения
В математике транзитивное замыкание однородного бинарного отношения R на множестве X — это наименьшее отношение на X, которое содержит R и является транзитивным. Для конечных множеств «наименьшее» понимается в обычном смысле, как отношение с наименьшим количеством связанных пар; для бесконечных множеств это единственное минимальное транзитивное надмножество R.
Например, если X — множество аэропортов, а x R y означает «существует прямой рейс из аэропорта x в аэропорт y» (для x и y из X), то транзитивное замыкание R на X — это отношение, такое что x R* y означает «возможно добраться из x в y за один или несколько рейсов». Более формально, транзитивное замыкание бинарного отношения R на множестве X — это наименьшее (относительно ⊆) транзитивное отношение на X, такое что R ⊆ R*. Мы имеем R* = R, если и только если R само по себе является транзитивным. Обратно, транзитивное сокращение позволяет получить минимальное отношение S из данного отношения R, такое что они имеют одно и то же замыкание, то есть R* = S*; однако, может существовать множество различных S с этим свойством. И транзитивное замыкание, и транзитивное сокращение также используются в тесно связанной области теории графов.
Транзитивные отношения и примеры
Отношение R на множестве X является транзитивным, если для всех x, y, z из X, всякий раз, когда x R y и y R z, то x R z. Примеры транзитивных отношений включают отношение равенства на любом множестве, отношение "меньше или равно" на любом линейно упорядоченном множестве и отношение "x родился раньше y" на множестве всех людей. Символически это можно обозначить как: если x < y и y < z, то x < z. Одним из примеров не транзитивного отношения является "из города y можно добраться прямым рейсом в город x" на множестве всех городов. Тот факт, что существует прямой рейс из одного города в другой, и прямой рейс из второго города в третий, не подразумевает наличие прямого рейса из первого города в третий. Транзитивное замыкание этого отношения – это другое отношение, а именно "существует последовательность прямых рейсов, начинающаяся в городе x и заканчивающаяся в городе y". Любое отношение можно аналогичным образом расширить до транзитивного отношения. Примером не транзитивного отношения с менее значимым транзитивным замыканием является "x – день недели, следующий за y". Транзитивное замыкание этого отношения – "существует день x, следующий за днем y в календаре", что тривиально верно для всех дней недели x и y (и, следовательно, эквивалентно декартовому квадрату, который представляет собой "x и y – оба дни недели").
Свойства
Пересечение двух транзитивных отношений является транзитивным. Объединение двух транзитивных отношений не обязательно транзитивно. Чтобы сохранить транзитивность, необходимо взять транзитивное замыкание. Это происходит, например, при объединении двух отношений эквивалентности или двух предпорядков. Для получения нового отношения эквивалентности или предпорядка необходимо взять транзитивное замыкание (рефлексивность и симметричность – в случае отношений эквивалентности – обеспечиваются автоматически).
В теории графов
В информатике концепция транзитивного замыкания может рассматриваться как построение структуры данных, позволяющей отвечать на вопросы о достижимости. То есть, можно ли добраться от узла a до узла d за один или несколько шагов? Бинарное отношение сообщает только, что узел a связан с узлом b, а узел b связан с узлом c и так далее. После построения транзитивного замыкания, как показано на следующем рисунке, за операцию O(1) можно определить, что узел d достижим из узла a. Обычно структура данных хранится в виде булевой матрицы, поэтому, если matrix[1][4] = true, то узел 1 может достичь узла 4 за один или несколько шагов. Транзитивное замыкание отношения смежности направленного ациклического графа (DAG) является отношением достижимости DAG и строгим частичным порядком. Транзитивное замыкание неориентированного графа порождает кластерный граф, представляющий собой непересекающееся объединение клик. Построение транзитивного замыкания эквивалентно задаче поиска компонент связности графа.
В языках запросов баз данных
С 1980-х годов Oracle Database реализовала собственное расширение SQL CONNECT BY START WITH, позволяющее вычислять транзитивное замыкание непосредственно в декларативном запросе. Стандарт SQL 3 (1999) добавил более общую конструкцию WITH RECURSIVE, также позволяющую вычислять транзитивное замыкание внутри обработчика запросов; по состоянию на 2011 год она реализована в IBM Db2, Microsoft SQL Server, Oracle, PostgreSQL и MySQL (v8.0+). SQLite добавила поддержку этой функции в 2014 году. Datalog также поддерживает вычисления транзитивного замыкания. MariaDB реализует рекурсивные общие табличные выражения, которые можно использовать для вычисления транзитивного замыкания. Эта функция была представлена в релизе 10.2.2 от апреля 2016 года.
Алгоритмы
Эффективные алгоритмы для вычисления транзитивного замыкания отношения смежности графа можно найти в подходе, сводящем задачу к умножению матриц смежности, что позволяет достичь наименьшей временной сложности, а именно сложности умножения матриц (O(n³)), которая, по состоянию на 2020 год, является оптимальной. Однако этот подход непрактичен из-за больших постоянных факторов и высокого потребления памяти для разреженных графов. Задача также может быть решена алгоритмом Флойда-Уоршалла за O(n³), или путем многократного поиска в ширину или глубину, начиная с каждого узла графа. Для ориентированных графов алгоритм Пурдома решает задачу, сначала вычисляя его конденсационный DAG и его транзитивное замыкание, а затем перенося результат на исходный граф. Его время работы составляет O(m), где m – количество ребер между сильно связными компонентами. Более поздние исследования посвящены эффективным способам вычисления транзитивного замыкания в распределенных системах на основе парадигмы MapReduce.