В математической области теории графов транзитивная редукция направленного графа D — это другой направленный граф с теми же вершинами и как можно меньшим количеством ребер, такой, что для всех пар вершин v , w (направленный) путь из v в w в D существует тогда и только тогда, когда такой путь существует в редукции. Транзитивные редукции были введены Ахо, Гари и Ульманом (1972), которые предоставили строгие границы вычислительной сложности их построения.
Более технически, редукция представляет собой ориентированный граф, который имеет то же отношение достижимости , что и D. Эквивалентно, D и его транзитивная редукция должны иметь то же самое транзитивное замыкание , что и друг у друга, а транзитивная редукция D должна иметь как можно меньше ребер среди всех графов с этим свойством.
Транзитивная редукция конечного ориентированного ациклического графа (ориентированного графа без направленных циклов ) является единственной и является подграфом данного графа. Однако, единственность не достигается для графов с (направленными) циклами, а для бесконечных графов даже существование не гарантируется.
Тесно связанное понятие минимального эквивалентного графа — это подграф D , который имеет то же отношение достижимости и как можно меньше ребер. [1] Разница в том, что транзитивная редукция не обязательно должна быть подграфом D. Для конечных направленных ациклических графов минимальный эквивалентный граф совпадает с транзитивной редукцией. Однако для графов, которые могут содержать циклы, минимально эквивалентные графы NP-трудны для построения, в то время как транзитивные редукции могут быть построены за полиномиальное время .
Транзитивную редукцию можно определить для абстрактного бинарного отношения на множестве , интерпретируя пары отношения как дуги в направленном графе.
Транзитивное сокращение конечного ориентированного графа G — это граф с наименьшим количеством возможных ребер, который имеет то же отношение достижимости, что и исходный граф. То есть, если есть путь из вершины x в вершину y в графе G , должен быть также путь из x в y в транзитивном сокращении G , и наоборот. В частности, если есть некоторый путь из 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]
Чтобы доказать, что транзитивное сокращение так же сложно, как и транзитивное замыкание, Ахо и др. строят из заданного направленного ациклического графа G другой граф H , в котором каждая вершина G заменена путем из трех вершин, а каждое ребро G соответствует ребру в H, соединяющему соответствующие средние вершины этих путей. Кроме того, в графе H Ахо и др. добавляют ребро от каждого начала пути до каждого конца пути. В транзитивном сокращении 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]
