Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В математике , А транзитивно сокращение из ориентированного графа D является еще ориентированным графом с теми же вершинами и , как несколько ребер , как это возможно, например , что для всех пар вершин V , W в (направленном) пути от V до W в D существует , если и только если такой путь существует в редукции. Транзитивные редукции были введены Aho, Garey & Ullman (1972) , которые дали жесткие ограничения на вычислительную сложность их построения.

Технически, сокращение представляет собой ориентированный граф , который имеет то же достижимость отношение как D . Эквивалентно, D и его транзитивная редукция должны иметь такое же транзитивное замыкание, что и друг друга, а транзитивная редукция D должна иметь как можно меньше ребер среди всех графов с этим свойством.

Транзитивная редукция конечного ориентированного ациклического графа (ориентированного графа без ориентированных циклов) единственна и является подграфом данного графа. Однако единственность не работает для графов с (направленными) циклами, а для бесконечных графов даже существование не гарантируется.

Тесно связанное понятие минимального эквивалентного графа - это подграф D, который имеет такое же отношение достижимости и как можно меньше ребер. [1] Разница заключается в том, что переходное снижение не должно быть подграфом D . Для конечных ориентированных ациклических графов минимальный эквивалентный граф совпадает с транзитивной редукцией. Однако для графов, которые могут содержать циклы, минимальные эквивалентные графы построить NP-сложно , в то время как транзитивные редукции могут быть построены за полиномиальное время .

Транзитивная редукция может быть определена для абстрактного бинарного отношения на множестве , интерпретируя пары отношения как дуги в ориентированном графе.

В ациклических ориентированных графах [ править ]

Транзитивная редукция конечного ориентированного графа G - это граф с наименьшим возможным количеством ребер, который имеет то же отношение достижимости, что и исходный граф. То есть, если существует путь от вершины x к вершине y в графе G , также должен быть путь от x к y в транзитивной редукции G , и наоборот. На следующем изображении показаны рисунки графиков, соответствующих нетранзитивному бинарному отношению (слева) и его транзитивной редукции (справа).

Тред-G.svgTred-Gprime.svg

Транзитивно снижение конечного ориентированный ациклического графа G является уникальным, и состоит из ребер G , которые образуют единственный путь между конечными точками их. В частности, это всегда подграф данного графа. По этой причине транзитивная редукция в этом случае совпадает с минимальным эквивалентным графом.

В математической теории бинарных отношений , никакое отношение R на множество X можно рассматривать как ориентированный граф , который имеет множество X в качестве своего множества вершин и что имеет дуги х для каждой упорядоченной пары элементов, которые связаны в R . В частности, этот метод позволяет интерпретировать частично упорядоченные множества как ориентированные ациклические графы, в которых есть дуга xy в графе всякий раз, когда существует отношение порядка x  <  yмежду данной парой элементов частичного порядка. Когда операция транзитивного сокращения применяется к ориентированному ациклическому графу, который был построен таким образом, он генерирует покрывающее отношение частичного порядка, которое часто визуально выражается с помощью диаграммы Хассе .

Транзитивная редукция использовалась в сетях, которые могут быть представлены как направленные ациклические графы (например, графы цитирования или сети цитирования ), чтобы выявить структурные различия между сетями. [2]

В графиках с циклами [ править ]

В конечном графе, имеющем циклы, транзитивная редукция может быть не уникальной: на одном наборе вершин может быть более одного графа, который имеет минимальное количество ребер и имеет такое же отношение достижимости, как данный граф. Кроме того, может случиться так, что ни один из этих минимальных графов не является подграфом данного графа. Тем не менее, это просто охарактеризовать минимальные графы с тем же соотношением, что достижимости данного графа G . [3] Если G - произвольный ориентированный граф, а H - граф с минимально возможным числом ребер, имеющих то же отношение достижимости, что и G , то H состоит из

  • Направлено цикл для каждого сильно связного компонента из G , соединяющие вершины вместе в этом компоненте
  • Ребро xy для каждого ребра XY транзитивной редукции сгущения группы G , где X и Y - две сильно связные компоненты группы G , соединенные ребром сгущения, x - любая вершина в компоненте X , а y - любая вершина в компоненте Y . Конденсация G - это ориентированный ациклический граф, у которого есть вершина для каждой сильно связной компоненты G и ребро для любых двух компонентов, соединенных ребром в G. В частности, поскольку он ацикличен, его транзитивная редукция может быть определена, как в предыдущем разделе.

Общее количество ребер в этом типе транзитивной редукции тогда равно количеству ребер в транзитивной редукции сгущения плюс количество вершин в нетривиальных сильно связных компонентах (компонентах с более чем одной вершиной).

Края переходного сокращения , которые соответствуют ребрам конденсации всегда могут быть выбраны , чтобы быть подграфом данного графа G . Однако цикл внутри каждой сильно связной компоненты может быть выбран как подграф G, только если этот компонент имеет гамильтонов цикл , что не всегда верно и трудно проверить. Из-за этой трудности найти наименьший подграф данного графа G с такой же достижимостью (его минимальный эквивалентный граф) NP-сложно . [3]

Вычислительная сложность [ править ]

Как Aho et al. показать [3], когда временная сложность алгоритмов графа измеряется только как функция числа n вершин в графе, а не как функция числа ребер, транзитивное замыкание и транзитивное сокращение ориентированных ациклических графов имеют такая же сложность. Это уже было показано , что транзитивное замыкание и умножение на булевых матрицы размера п  ×  п имело такую же сложность , как друг с другом, [4] , поэтому этот результат поместить переходное снижение в том же класс. Самые быстрые из известных точных алгоритмов умножения матриц по состоянию на 2015 год занимают время O ( n 2,3729 ),[5], и это дает самую быструю из известных наихудших временных рамок для транзитивного сокращения плотных графов.

Вычисление сокращения с использованием замыкания [ править ]

Чтобы доказать, что транзитивная редукция так же проста, как транзитивное замыкание, Aho et al. полагаться на уже известную эквивалентность с умножением булевых матриц. Они позволяют 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 ( нм) временная граница соответствует сложности построения транзитивных замыканий с использованием поиска в глубину или поиска в ширину, чтобы найти вершины, достижимые при любом выборе начальной вершины, поэтому снова с этими предположениями транзитивные замыкания и транзитивные сокращения могут быть найдены за то же время. .

Заметки [ править ]

  1. ^ Moyles & Thompson (1969) .
  2. ^ Клаф и др. (2015) .
  3. ^ a b c d e Aho, Garey & Ullman (1972)
  4. ^ Ахо и др. приписывают этот результат неопубликованной рукописи Яна Манро 1971 года и русскоязычной статье 1970 года М.Е. Фурмана.
  5. Перейти ↑ Le Gall (2014) .

Ссылки [ править ]

  • Ахо, А.В .; Garey, MR ; Ульмана, JD (1972), "переходное сокращение ориентированного графа", SIAM журнал по вычислениям , 1 (2): 131-137, DOI : 10,1137 / 0201008 , МР  0306032.
  • Клаф, младший; Gollings, J .; Вьюн, телевизор; Эванс, Т.С. (2015), «Переходное сокращение сетей цитирования», Журнал сложных сетей , 3 (2): 189–203, arXiv : 1310.8224 , doi : 10.1093 / comnet / cnu039.
  • Moyles, Dennis M .; Томпсон, Джеральд Л. (1969), «Алгоритм поиска минимального Эквивалент график Орграф», Журнал ACM , 16 (3): 455-460, DOI : 10,1145 / 321526,321534.
  • Ле Галл, Франсуа (2014), «Степени тензоров и быстрое умножение матриц», Proc. 39 - й Международный симпозиум по символическим и алгебраическим вычислениям (ИССАК '14) . С. 296-303, DOI : 10,1145 / 2608628,2608664.

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. «Переходная редукция» . MathWorld .