Транзитивное сокращение ориентированного графа

Введение

Копия направленного графа с удаленными избыточными ребрами.

В математической области теории графов, транзитивное уменьшение направленного графа D – это другой направленный граф с теми же вершинами и минимально возможным количеством ребер, таким образом, что для любой пары вершин v и w (направленный) путь из v в w в D существует тогда и только тогда, когда такой путь существует в уменьшении. Транзитивные уменьшения были введены [имя автора], который установил точные границы вычислительной сложности их построения. Более технически, уменьшение – это направленный граф, имеющий такое же отношение достижимости, как и D. Эквивалентно, D и его транзитивное уменьшение должны иметь одинаковое транзитивное замыкание, а транзитивное уменьшение D должно иметь минимальное количество ребер среди всех графов, обладающих этим свойством. Транзитивное уменьшение конечного направленного ациклического графа (направленного графа без направленных циклов) является единственным и является подграфом исходного графа. Однако единственность не выполняется для графов с (направленными) циклами, а для бесконечных графов даже существование не гарантируется. Тесно связанное понятие минимально эквивалентного графа – это подграф D, имеющий такое же отношение достижимости и минимальное количество ребер. Отличие состоит в том, что транзитивное уменьшение не обязательно должно быть подграфом 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 является множеством его вершин, а для каждой упорядоченной пары элементов, связанных в R, существует дуга xy. В частности, этот метод позволяет переинтерпретировать частично упорядоченные множества как ориентированные ациклические графы, в которых в графе существует дуга xy всякий раз, когда между данной парой элементов частичного порядка существует отношение порядка x < y. Применение операции транзитивной редукции к ориентированному ациклическому графу, построенному таким образом, генерирует отношение покрытия частичного порядка, которое часто визуализируется с помощью диаграммы Хассе. Транзитивная редукция использовалась для анализа сетей, которые могут быть представлены в виде ориентированных ациклических графов (например, графов цитирования или сетей цитирования), для выявления структурных различий между сетями.

Вычисление уменьшения с использованием закрытия

Чтобы доказать, что транзитивное уменьшение не сложнее транзитивного замыкания, Aho и др. опираются на известную эквивалентность с умножением булевых матриц. Они рассматривают A как матрицу смежности заданного ориентированного ациклического графа, а B – как матрицу смежности его транзитивного замыкания (вычисленного с помощью любого стандартного алгоритма транзитивного замыкания). Тогда ребро uv принадлежит транзитивному уменьшению тогда и только тогда, когда в строке u и столбце v матрицы A есть ненулевой элемент, а в той же позиции произведения матриц AB – нулевой. В данной конструкции ненулевые элементы матрицы AB представляют собой пары вершин, соединенных путями длиной два или более.

Вычисление закрытия с использованием уменьшения

Чтобы доказать, что транзитивное уменьшение не проще, чем транзитивное замыкание, Aho и др. строят из заданного ориентированного ациклического графа G другой граф H, в котором каждая вершина G заменяется путем из трех вершин, а каждому ребру G соответствует ребро в H, соединяющее соответствующие средние вершины этих путей. Кроме того, в графе H, Aho и др. добавляют ребро от начала каждого пути к концу каждого пути. В транзитивном уменьшении H существует ребро от начала пути для u к концу пути для v тогда и только тогда, когда ребро uv не принадлежит транзитивному замыканию G. Следовательно, если транзитивное уменьшение H может быть вычислено эффективно, транзитивное замыкание G можно непосредственно получить из него.

Вычисление уменьшения в разреженных графах

При измерении как по количеству вершин n, так и по количеству ребер m в ориентированном ациклическом графе, транзитивные сокращения также могут быть найдены за время O(nm), что может быть быстрее, чем методы умножения матриц для разреженных графов. Для этого примените алгоритм поиска самого длинного пути за линейное время в данном ориентированном ациклическом графе для каждого возможного выбора начальной вершины. Из вычисленных самых длинных путей сохраняйте только те, которые имеют длину один (состоящие из одного ребра); иными словами, сохраняйте те ребра (u, v), для которых не существует другого пути из u в v. Эта временная сложность O(nm) соответствует сложности построения транзитивных замыканий с использованием поиска в глубину или поиска в ширину для нахождения вершин, достижимых из каждого выбора начальной вершины, поэтому, при тех же предположениях, транзитивные замыкания и транзитивные сокращения могут быть найдены за одинаковое время.