В математической области теории графов транзитивная редукция ориентированного графа D — это другой ориентированный граф с теми же вершинами и как можно меньшим количеством ребер, такой, что для всех пар вершин v , wa (ориентированный) путь от v до w в D существует тогда и только тогда, когда такой путь существует в редукции. Транзитивные редукции были введены Ахо, Гари и Ульманом (1972), которые установили жесткие ограничения на вычислительную сложность их построения.
С технической точки зрения, сокращение представляет собой ориентированный граф, который имеет то же отношение достижимости , что и D . Эквивалентно, D и его транзитивная редукция должны иметь такое же транзитивное замыкание , как и друг друга, а транзитивная редукция D должна иметь как можно меньше ребер среди всех графов с этим свойством.
Транзитивная редукция конечного ориентированного ациклического графа (ориентированного графа без ориентированных циклов ) единственна и является подграфом данного графа. Однако уникальность невозможна для графов с (ориентированными) циклами, а для бесконечных графов даже существование не гарантируется.
Тесно связанная концепция минимального эквивалентного графа — это подграф D , который имеет то же отношение достижимости и минимально возможное количество ребер. [1] Разница в том, что транзитивная редукция не обязательно должна быть подграфом D . Для конечных ориентированных ациклических графов минимальный эквивалентный граф совпадает с транзитивной редукцией. Однако для графов, которые могут содержать циклы, минимальные эквивалентные графы построить NP-трудно , а транзитивные редукции можно построить за полиномиальное время .
Транзитивную редукцию можно определить для абстрактного бинарного отношения на множестве , интерпретируя пары отношения как дуги в ориентированном графе.
Транзитивная редукция конечного ориентированного графа G — это граф с наименьшим количеством возможных ребер, имеющий то же отношение достижимости , что и исходный граф. То есть, если в графе G существует путь от вершины x к вершине y , то в транзитивной редукции G также должен существовать путь от x до y , и наоборот. В частности, если существует некоторый путь от x до y и другой от y до z, то не может быть пути от x до z, который не включал бы y. Транзитивность для x, y и z означает, что если x < y и y < z, то x < z. Если для любого пути от y до z существует путь от x до y, то существует путь от x до z; однако неверно, что для любых путей от x до y и от x до z существует путь от y до z, и поэтому любое ребро между вершинами x и z исключается при транзитивной редукции, поскольку они представляют собой маршруты, которые не являются транзитивными. . На следующем изображении показаны рисунки графиков, соответствующих нетранзитивному бинарному отношению (слева) и его транзитивному сокращению (справа).
Транзитивная редукция конечного ориентированного ациклического графа G уникальна и состоит из ребер G , которые образуют единственный путь между своими конечными точками. В частности, это всегда остовный подграф данного графа. По этой причине транзитивная редукция в этом случае совпадает с минимальным эквивалентным графом.
В математической теории бинарных отношений любое отношение R на множестве X можно рассматривать как ориентированный граф , который имеет множество X в качестве множества вершин и имеет дугу xy для каждой упорядоченной пары элементов , связанных в R. В частности, этот метод позволяет переинтерпретировать частично упорядоченные множества как ориентированные ациклические графы, в которых дуга xy присутствует в графе всякий раз, когда существует отношение порядка x < y между заданной парой элементов частичного порядка. Когда операция транзитивной редукции применяется к построенному таким образом ориентированному ациклическому графу, она порождает накрывающее отношение частичного порядка, которому часто дают наглядное выражение с помощью диаграммы Хассе .
Транзитивная редукция использовалась в сетях, которые могут быть представлены как направленные ациклические графы (например, графы цитирования или сети цитирования ), чтобы выявить структурные различия между сетями. [2]
В конечном графе, имеющем циклы, транзитивная редукция может быть не единственной: на одном и том же множестве вершин может существовать более одного графа, который имеет минимальное количество ребер и имеет то же отношение достижимости, что и данный граф. Кроме того, может случиться так, что ни один из этих минимальных графов не является подграфом данного графа. Тем не менее, минимальные графы несложно охарактеризовать тем же отношением достижимости, что и данный граф G . [3] Если G — произвольный ориентированный граф, а H — граф с минимально возможным числом ребер, имеющий то же отношение достижимости, что и G , то H состоит из
Общее количество ребер в этом типе транзитивной редукции тогда равно количеству ребер в транзитивной редукции конденсации плюс числу вершин в нетривиальных сильно связных компонентах (компонентах с более чем одной вершиной).
Ребра транзитивной редукции, соответствующие ребрам конденсации, всегда можно выбрать в качестве подграфа данного графа G . Однако цикл внутри каждого сильно связного компонента может быть выбран в качестве подграфа G только в том случае, если этот компонент имеет гамильтонов цикл , что не всегда верно и его трудно проверить. Из-за этой трудности NP-трудно найти наименьший подграф данного графа G с одинаковой достижимостью (его минимальный эквивалентный граф). [3]
Ахо и др. приведите следующий пример, чтобы показать, что в бесконечных графах , даже если граф ациклический, транзитивная редукция может не существовать. Сформируйте граф с вершиной для каждого действительного числа и с ребром всякий раз, когда это действительные числа. Тогда этот граф бесконечен, ацикличен и транзитивно замкнут. Однако в любом подграфе, имеющем такое же транзитивное замыкание, каждое оставшееся ребро можно удалить, не меняя транзитивное замыкание, поскольку все равно должен оставаться путь от до через любую вершину между ними. Следовательно, среди подграфов с одинаковым транзитивным замыканием ни один из этих подграфов не является минимальным: транзитивной редукции нет. [3]
Как Ахо и др. показывают, [3] когда временная сложность графовых алгоритмов измеряется только как функция числа n вершин в графе, а не как функция числа ребер, транзитивное замыкание и транзитивная редукция ориентированных ациклических графов имеют та же сложность. Уже было показано, что транзитивное замыкание и умножение булевых матриц размера n × n имеют одинаковую сложность, [4] поэтому этот результат отнес транзитивную редукцию к одному и тому же классу. Наилучшие точные алгоритмы умножения матриц по состоянию на 2023 год требуют времени O( n 2,371552 ), [5] , и это дает самую быструю из известных оценок времени для наихудшего случая для транзитивной редукции в плотных графах.
Чтобы доказать, что транзитивная редукция так же проста, как и транзитивное замыкание, Ахо и др. полагаться на уже известную эквивалентность с умножением булевых матриц. Они позволяют A быть матрицей смежности данного ориентированного ациклического графа, а B — матрицей смежности его транзитивного замыкания (вычисленной с использованием любого стандартного алгоритма транзитивного замыкания). Тогда ребро uv принадлежит транзитивной редукции тогда и только тогда, когда существует ненулевой элемент в строке u и столбце v матрицы A и существует нулевой элемент в той же позиции матричного произведения AB . В этой конструкции ненулевые элементы матрицы AB представляют собой пары вершин, соединенных путями длины два и более. [3]
Чтобы доказать, что транзитивная редукция так же сложна, как и транзитивное замыкание, Aho et al. построить из заданного ориентированного ациклического графа G другой граф H , в котором каждая вершина G заменена путем из трех вершин, а каждому ребру G соответствует ребро в H , соединяющее соответствующие средние вершины этих путей. Кроме того, на графике H Aho et al. добавьте ребро от начала каждого пути до конца каждого пути. При транзитивной редукции H существует ребро от начала пути u до конца пути v тогда и только тогда, когда ребро uv не принадлежит транзитивному замыканию G . Следовательно, если транзитивную редукцию H можно эффективно вычислить, транзитивное замыкание G можно считать непосредственно из нее. [3]
При измерении как по количеству n вершин, так и по количеству m ребер в ориентированном ациклическом графе, транзитивные сокращения также могут быть найдены за время O( nm ), оценка, которая может быть быстрее, чем методы матричного умножения для разреженных графов. . Для этого примените алгоритм поиска наибольшего пути с линейным временем в заданном ориентированном ациклическом графе для каждого возможного выбора начальной вершины. Из вычисленных самых длинных путей оставьте только те, длина которых равна единице (одиночное ребро); другими словами, сохраните те ребра ( u , v ), для которых не существует другого пути от u до v . Эта граница времени O( nm ) соответствует сложности построения транзитивных замыканий с использованием поиска в глубину или поиска в ширину для нахождения вершин, достижимых из любого выбора начальной вершины, поэтому снова с этими предположениями транзитивные замыкания и транзитивные сокращения могут быть найдены в такое же количество времени.
Для графа с n вершинами, m ребрами и r ребрами в транзитивной редукции можно найти транзитивную редукцию с помощью алгоритма, чувствительного к выходу, за время, которое зависит от r вместо m . Алгоритм следующий: [6]
Упорядочение ребер во внутреннем цикле можно получить, используя два прохода сортировки по счету или другой устойчивый алгоритм сортировки для сортировки ребер, сначала по топологической нумерации их конечной вершины, а затем по их начальной вершине. Если множества представлены в виде битовых массивов , каждая операция объединения множеств может быть выполнена за время O ( n ) или быстрее с использованием побитовых операций . Количество этих операций над множествами пропорционально количеству выходных ребер, что приводит к общему ограничению времени O ( nr ). Множества достижимости, полученные в ходе алгоритма, описывают транзитивное замыкание входа. [6]
Если граф задан вместе с разбиением его вершин на k цепей (попарно достижимых подмножеств), это время можно дополнительно сократить до O ( kr ), кратко представив каждое достижимое множество как объединение суффиксов цепей. [7]
