Транзитивная редукция

В математической области теории графов транзитивная редукция D ориентированного графа — это другой ориентированный граф с теми же вершинами и как можно меньшим количеством ребер, такой, что для всех пар вершин v , wa (ориентированный) путь от v до w в D существует тогда и только тогда, когда такой путь существует в редукции. Транзитивные редукции были введены Ахо, Гари и Ульманом (1972) , которые установили жесткие ограничения на вычислительную сложность их построения.

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

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

Близко связанное понятие минимального эквивалентного графа — это подграф D , который имеет то же отношение достижимости и минимально возможное количество ребер. что транзитивная редукция не обязательно должна быть подграфом 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 между данной парой элементов частичного порядка. Когда операция транзитивной редукции применяется к построенному таким образом ориентированному ациклическому графу, она порождает накрывающее отношение частичного порядка, которому часто дают наглядное выражение с помощью диаграммы Хассе .

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

В графиках с циклами

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

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

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

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

В бесконечных графах

Ахо и др. приведите следующий пример, чтобы показать, что в бесконечных графах , даже если граф является ациклическим, транзитивная редукция может не существовать. Сформируйте граф с вершиной для каждого действительного числа , с ребром $x\to y$ в любое время $x<y$ как реальные числа. Тогда этот граф бесконечен, ацикличен и транзитивно замкнут. Однако в любом подграфе, имеющем такое же транзитивное замыкание, каждое оставшееся ребро $x\to y$ можно удалить, не меняя транзитивного замыкания, поскольку все равно должен остаться путь от $x$ к $y$ через любую вершину между ними. Следовательно, среди подграфов с одинаковым транзитивным замыканием ни один из этих подграфов не является минимальным: транзитивной редукции нет.

Вычислительная сложность

Как Ахо и др. показывать, когда временная сложность графовых алгоритмов измеряется только как функция числа n вершин в графе, а не как функция количества ребер, транзитивное замыкание и транзитивная редукция ориентированных ациклических графов имеют одинаковую сложность. Уже было показано, что транзитивное замыкание и умножение булевых матриц размера n × n имеют одинаковую сложность друг с другом: таким образом, этот результат поместил транзитивную редукцию в тот же класс. Лучшие точные алгоритмы умножения матриц по состоянию на 2023 год занимают время O( n ^2.371552 ), и это дает самую быструю из известных оценок времени для наихудшего случая для транзитивной редукции в плотных графах, применяя ее к матрицам над целыми числами и просматривая ненулевые записи в результате.

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

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

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

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

Вычисление сокращения разреженных графов

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

Чувствителен к выходу

Для графа с n вершинами, m ребрами и r ребрами в транзитивной редукции можно найти транзитивную редукцию с помощью алгоритма, чувствительного к выходу, за время, которое зависит от r вместо m . Алгоритм:

• Для каждой вершины v в порядке, обратном топологическому порядку входного графа:
  • Инициализируйте набор вершин, достижимых из v , первоначально одноэлементный набор { v }.
  • Для каждого ребра vw в топологическом порядке w проверьте, находится ли w в множестве достижимости v , а если нет:
    • Выходной край vw как часть транзитивной редукции.
    • Замените набор вершин, достижимых из v , его объединением с множеством достижимых вершин w .

Упорядочение ребер во внутреннем цикле можно получить, используя два прохода сортировки по счету или другой устойчивый алгоритм сортировки для сортировки ребер, сначала по топологической нумерации их конечной вершины, а во-вторых, по их начальной вершине. Если множества представлены в виде битовых массивов , каждая операция объединения множеств может быть выполнена за время O ( n ) или быстрее с использованием побитовых операций . Количество этих операций над множествами пропорционально количеству выходных ребер, что приводит к общему ограничению времени O ( nr ). Множества достижимости, полученные в ходе алгоритма, описывают транзитивное замыкание входа.

Если граф задан вместе с разбиением его вершин на k цепей (попарно достижимых подмножеств), это время можно дополнительно сократить до O ( kr ), кратко представив каждое достижимое множество как объединение суффиксов цепей.

Ссылки

• Ахо, А.В .; Гэри, MR ; Уллман, Дж. Д. (1972), «Транзитивная редукция ориентированного графа», SIAM Journal on Computing , 1 (2): 131–137, doi : 10.1137/0201008 , MR   0306032 .
• Клаф, младший; Голлингс, Дж.; Лоуч, ТВ; Эванс, Т.С. (2015), «Транзитивное сокращение сетей цитирования», Journal of Complex Networks , 3 (2): 189–203, arXiv : 1310.8224 , doi : 10.1093/comnet/cnu039 .
• Фурман М.Е. (1970), "Применение метода быстрого умножения матриц к задаче нахождения транзитивного замыкания графа" , Доклады АН СССР , 194 : 524, МР   0270950
• Горальчикова Алла; Коубек, Вацлав (1979), «Алгоритм сокращения и замыкания для графов», в Бецваре, Ири (редактор), «Математические основы информатики», 1979 г., материалы 8-го симпозиума, Оломоуц, Чехословакия, 3-7 сентября 1979 г. , Конспекты лекций по информатике, вып. 74, Springer, стр. 301–307, номер документа : 10.1007/3-540-09526-8_27 .
• Мойлс, Деннис М.; Томпсон, Джеральд Л. (1969), «Алгоритм поиска минимального эквивалентного графа орграфа», Журнал ACM , 16 (3): 455–460, doi : 10.1145/321526.321534 .
• Саймон, Клаус (1988), «Улучшенный алгоритм транзитивного замыкания ациклических орграфов», Theoretical Computer Science , 58 (1–3): 325–346, doi : 10.1016/0304-3975(88)90032-1 , MR   0963268 .
• Уильямс, Вирджиния Василевска ; Сюй, Иньчжан; Сюй, Цзысюань; Чжоу, Ренфэй (2023), Новые границы умножения матриц: от альфа до омеги , arXiv : 2307.07970 .

Внешние ссылки

• Вайсштейн, Эрик В. , «Транзитивная редукция» , MathWorld