Достижимость

Можно ли достичь одной вершины из другой в графе

В теории графов достижимость относится к возможности добраться из одной вершины в другую в пределах графа. Вершина может достичь вершины (и достижима из ), если существует последовательность смежных вершин (т.е. путь ), которая начинается с и заканчивается . ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle t}$

В неориентированном графе достижимость между всеми парами вершин может быть определена путем идентификации связных компонентов графа. Любая пара вершин в таком графе может достигать друг друга тогда и только тогда, когда они принадлежат одному и тому же связному компоненту; следовательно, в таком графе достижимость симметрична ( достигает тогда и только тогда, когда достигает ). Связные компоненты неориентированного графа могут быть идентифицированы за линейное время. Оставшаяся часть этой статьи посвящена более сложной задаче определения попарной достижимости в ориентированном графе (который, кстати, не обязательно должен быть симметричным). ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle s}$

Определение

Для ориентированного графа с множеством вершин и множеством ребер отношение достижимости является транзитивным замыканием , то есть множеством всех упорядоченных пар вершин в , для которых существует последовательность вершин такая, что ребро находится в для всех . ^[1] ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle G}$ ${\displaystyle E}$ ${\displaystyle (s,t)}$ ${\displaystyle V}$ ${\displaystyle v_{0}=s,v_{1},v_{2},...,v_{k}=t}$ ${\displaystyle (v_{i-1},v_{i})}$ ${\displaystyle E}$ ${\displaystyle 1\leq i\leq k}$

Если является ациклическим , то его отношение достижимости является частичным порядком ; любой частичный порядок может быть определен таким образом, например, как отношение достижимости его транзитивной редукции . ^[2] Примечательным следствием этого является то, что поскольку частичные порядки антисимметричны, если может достичь , то мы знаем, что не может достичь . Интуитивно, если бы мы могли перемещаться от до и обратно к , то содержал бы цикл , что противоречит тому, что он ацикличен. Если является направленным, но не ацикличным (т.е. он содержит по крайней мере один цикл), то его отношение достижимости будет соответствовать предпорядку вместо частичного порядка. ^[3] ${\displaystyle G}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle G}$ ${\displaystyle G}$

Алгоритмы

Алгоритмы определения достижимости делятся на два класса: требующие предварительной обработки и не требующие ее.

Если у вас есть только один (или несколько) запросов, может быть более эффективным отказаться от использования более сложных структур данных и вычислить достижимость нужной пары напрямую. Это может быть достигнуто за линейное время с использованием таких алгоритмов, как поиск в ширину или итеративное углубление поиска в глубину . ^[4]

Если вы будете делать много запросов, то можно использовать более сложный метод; точный выбор метода зависит от природы анализируемого графа. В обмен на время предварительной обработки и некоторое дополнительное пространство для хранения мы можем создать структуру данных, которая затем сможет отвечать на запросы достижимости для любой пары вершин всего за время. Ниже описаны три различных алгоритма и структуры данных для трех различных, все более специализированных ситуаций. ${\displaystyle O(1)}$

Алгоритм Флойда-Уоршелла

Алгоритм Флойда–Уоршелла ^[5] можно использовать для вычисления транзитивного замыкания любого ориентированного графа, что приводит к отношению достижимости, как в определении выше.

Алгоритм требует времени и пространства в худшем случае. Этот алгоритм не интересуется только достижимостью, поскольку он также вычисляет кратчайшее расстояние между всеми парами вершин. Для графов, содержащих отрицательные циклы, кратчайшие пути могут быть неопределенными, но достижимость между парами все еще может быть отмечена. ${\displaystyle O(|V|^{3})}$ ${\displaystyle O(|V|^{2})}$

Алгоритм Торупа

Для планарных орграфов доступен гораздо более быстрый метод, описанный Миккелем Торупом в 2004 году. ^[6] Этот метод может отвечать на запросы о достижимости на планарном графе за время после затрат времени предварительной обработки для создания структуры данных размера. Этот алгоритм также может предоставлять приблизительные кратчайшие расстояния пути, а также информацию о маршруте. ${\displaystyle O(1)}$ ${\displaystyle O(n\log {n})}$ ${\displaystyle O(n\log {n})}$

Общий подход заключается в том, чтобы связать с каждой вершиной относительно небольшой набор так называемых путей-разделителей, так что любой путь от вершины до любой другой вершины должен проходить по крайней мере через один из разделителей, связанных с или . Далее следует схема разделов, связанных с достижимостью. ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle w}$

При наличии графа алгоритм начинается с организации вершин в слои, начиная с произвольной вершины . Слои строятся поочередно, сначала рассматривая все вершины, достижимые с предыдущего шага (начиная с просто ), а затем все вершины, которые достигают предыдущего шага, пока все вершины не будут назначены слою. По построению слоев каждая вершина появляется не более чем в двух слоях, и каждый направленный путь , или дипут, в содержится в двух соседних слоях и . Пусть будет последним созданным слоем, то есть наименьшим значением для такого, что . ${\displaystyle G}$ ${\displaystyle v_{0}}$ ${\displaystyle v_{0}}$ ${\displaystyle G}$ ${\displaystyle L_{i}}$ ${\displaystyle L_{i+1}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \bigcup _{i=0}^{k}L_{i}=V}$

Граф затем переформулируется как ряд орграфов , где каждый и где является сжатием всех предыдущих уровней в одну вершину. Поскольку каждый дипат появляется не более чем в двух последовательных слоях, и поскольку каждый образован двумя последовательными слоями, каждый дипат в появляется полностью по крайней мере в одном (и не более чем в 2 последовательных таких графах) ${\displaystyle G_{0},G_{1},\ldots ,G_{k-1}}$ ${\displaystyle G_{i}=r_{i}\cup L_{i}\cup L_{i+1}}$ ${\displaystyle r_{i}}$ ${\displaystyle L_{0}\ldots L_{i-1}}$ ${\displaystyle G_{i}}$ ${\displaystyle G}$ ${\displaystyle G_{i}}$

Для каждого определяются три сепаратора, которые при удалении разбивают граф на три компонента, каждый из которых содержит не более вершин исходного. Поскольку он построен из двух слоев противоположных дипутов, каждый сепаратор может состоять из 2 дипутов, в общей сложности до 6 дипутов по всем сепараторам. Пусть будет этим набором дипутов. Доказательство того, что такие сепараторы всегда можно найти, связано с теоремой о плоском сепараторе Липтона и Тарьяна, и эти сепараторы можно найти за линейное время. ${\displaystyle G_{i}}$ ${\displaystyle 1/2}$ ${\displaystyle G_{i}}$ ${\displaystyle S}$

Для каждого направленная природа обеспечивает естественную индексацию его вершин от начала до конца пути. Для каждой вершины в мы находим первую вершину в достижимую по , и последнюю вершину в , которая достигает . То есть, мы смотрим, как рано в мы можем попасть из , и как далеко мы можем остаться и все равно вернуться в . Эта информация хранится с каждым . Затем для любой пары вершин и , можно добраться через , если соединяется с раньше, чем соединяется с . ${\displaystyle Q\in S}$ ${\displaystyle Q}$ ${\displaystyle v}$ ${\displaystyle G_{i}}$ ${\displaystyle Q}$ ${\displaystyle v}$ ${\displaystyle Q}$ ${\displaystyle v}$ ${\displaystyle Q}$ ${\displaystyle v}$ ${\displaystyle Q}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle w}$ ${\displaystyle u}$ ${\displaystyle w}$ ${\displaystyle Q}$ ${\displaystyle u}$ ${\displaystyle Q}$ ${\displaystyle w}$ ${\displaystyle Q}$

Каждая вершина помечена, как указано выше, для каждого шага рекурсии, которая строит . Поскольку эта рекурсия имеет логарифмическую глубину, общая дополнительная информация хранится на вершину. С этой точки зрения логарифмический запрос времени для достижимости так же прост, как просмотр каждой пары меток для общего, подходящего . Затем исходная статья работает над тем, чтобы уменьшить время запроса до . ${\displaystyle G_{0}\ldots ,G_{k}}$ ${\displaystyle O(\log {n})}$ ${\displaystyle Q}$ ${\displaystyle O(1)}$

Подводя итоги анализа этого метода, сначала учтите, что подход с использованием слоев разбивает вершины так, что каждая вершина рассматривается только один раз. Фаза сепаратора алгоритма разбивает граф на компоненты, которые имеют размер не более исходного графа, что приводит к логарифмической глубине рекурсии. На каждом уровне рекурсии требуется только линейная работа для определения сепараторов, а также возможных связей между вершинами. Общий результат — это время предварительной обработки с сохранением только дополнительной информации для каждой вершины. ${\displaystyle O(1)}$ ${\displaystyle 1/2}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(\log {n})}$

Алгоритм Камеды

Подходящий орграф для метода Камеды с добавлением и . ${\displaystyle s}$ ${\displaystyle t}$

Тот же график, что и выше, после запуска алгоритма Камеды, показывающий метки DFS для каждой вершины

Еще более быстрый метод предварительной обработки, предложенный Т. Камедой в 1975 году ^[7], можно использовать, если граф является плоским , ациклическим и также обладает следующими дополнительными свойствами: все вершины с 0- степенью вхождения и все вершины с 0-степенью исхода находятся на одной грани (часто предполагаемой внешней), и границу этой грани можно разбить на две части так, чтобы все вершины с 0-степенью вхождения находились на одной части, а все вершины с 0-степенью исхода — на другой (т. е. два типа вершин не чередуются).

Если он обладает этими свойствами, то мы можем выполнить предварительную обработку графа всего за одно время и сохранить только дополнительные биты на вершину, отвечая на запросы о достижимости для любой пары вершин во времени с помощью простого сравнения. ${\displaystyle G}$ ${\displaystyle O(n)}$ ${\displaystyle O(\log {n})}$ ${\displaystyle O(1)}$

Предварительная обработка выполняет следующие шаги. Мы добавляем новую вершину , которая имеет ребро к каждой вершине с 0-й степенью вхождения, и еще одну новую вершину с ребрами из каждой вершины с 0-й степенью исхода. Обратите внимание, что свойства позволяют нам делать это, сохраняя планарность, то есть после этих добавлений по-прежнему не будет пересечений ребер. Для каждой вершины мы сохраняем список смежностей (исходящих ребер) в порядке планарности графа (например, по часовой стрелке относительно вложения графа). Затем мы инициализируем счетчик и начинаем обход в глубину с . Во время этого обхода список смежностей каждой вершины посещается слева направо по мере необходимости. По мере того, как вершины извлекаются из стека обхода, они помечаются значением , а затем уменьшаются. Обратите внимание, что всегда помечается значением и всегда помечается . Затем обход в глубину повторяется, но на этот раз список смежности каждой вершины просматривается справа налево. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle G}$ ${\displaystyle i=n+1}$ ${\displaystyle s}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle t}$ ${\displaystyle n+1}$ ${\displaystyle s}$ ${\displaystyle 0}$

После завершения и , и их инцидентные ребра удаляются. Каждая оставшаяся вершина хранит двумерную метку со значениями от до . При наличии двух вершин и , и их меток и , мы говорим, что тогда и только тогда , когда , , и существует по крайней мере один компонент или , который строго меньше или , соответственно. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle L(u)=(a_{1},a_{2})}$ ${\displaystyle L(v)=(b_{1},b_{2})}$ ${\displaystyle L(u)<L(v)}$ ${\displaystyle a_{1}\leq b_{1}}$ ${\displaystyle a_{2}\leq b_{2}}$ ${\displaystyle a_{1}}$ ${\displaystyle a_{2}}$ ${\displaystyle b_{1}}$ ${\displaystyle b_{2}}$

Основной результат этого метода утверждает, что достижимо из тогда и только тогда , когда , что легко вычисляется со временем. ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle L(u)<L(v)}$ ${\displaystyle O(1)}$

Связанные проблемы

Связанная проблема заключается в решении запросов достижимости с некоторым количеством отказов вершин. Например: «Может ли вершина все еще достичь вершины, даже если вершины вышли из строя и больше не могут использоваться?» Похожая проблема может рассматривать отказы ребер, а не отказы вершин, или сочетание того и другого. Метод поиска в ширину работает так же хорошо для таких запросов, но построение эффективного оракула более сложно. ^{[8] [9]} ${\displaystyle k}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle s_{1},s_{2},...,s_{k}}$

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

Смотрите также

• Гаммоид
• st -связность

Ссылки

1. Скиена, Стивен С. (2011), «15.5 Транзитивное замыкание и редукция», Руководство по разработке алгоритмов (2-е изд.), Springer, стр. 495–497, ISBN 9781848000698.
2. Кон, Пол Мориц (2003), Основы алгебры: группы, кольца и поля, Springer, стр. 17, ISBN 9781852335878.
3. Шмидт, Гюнтер (2010), Реляционная математика, Энциклопедия математики и ее приложений, т. 132, Cambridge University Press, стр. 77, ISBN 9780521762687.
4. Герстинг, Джудит Л. (2006), Математические структуры для компьютерных наук (6-е изд.), Macmillan, стр. 519, ISBN 9780716768647.
5. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2001), «Транзитивное замыкание ориентированного графа», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 632–634, ISBN 0-262-03293-7.
6. Торуп, Миккель (2004), «Компактные оракулы для достижимости и приблизительных расстояний в планарных орграфах», Журнал ACM , 51 (6): 993–1024, doi :10.1145/1039488.1039493, MR  2145261, S2CID  18864647.
7. Камеда, Т (1975), «О векторном представлении достижимости в плоских ориентированных графах», Information Processing Letters , 3 (3): 75–77, doi :10.1016/0020-0190(75)90019-8.
8. Деметреску, Камил; Торуп, Миккель ; Чоудхури, Резаул Алам; Рамачандран, Виджая (2008), «Оракулы для определения расстояний, позволяющих избежать отказа узла или канала», SIAM Journal on Computing , 37 (5): 1299–1318, CiteSeerX 10.1.1.329.5435 , doi : 10.1137/S0097539705429847, MR  2386269 .
9. Халфтермейер, Пьер, Связность в сетях и компактные схемы маркировки для планирования действий в чрезвычайных ситуациях, Университет Бордо.