Доступность

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

В теории графов достижимость означает возможность перейти из одной вершины в другую внутри графа. Вершина может достичь вершины (и достижима из ), если существует последовательность соседних вершин (т.е. обход ), которая начинается с и заканчивается с . ${\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}$

Учитывая граф , алгоритм начинает с организации вершин в слои, начиная с произвольной вершины . Слои создаются чередующимися шагами: сначала рассматриваются все вершины, достижимые на предыдущем шаге (начиная с просто ), а затем все вершины, которые достигают предыдущего шага, пока все вершины не будут назначены слою. По построению слоев каждая вершина появляется не более чем в двух слоях, и каждый направленный путь или dipath в содержится в двух соседних слоях и . Пусть будет последний созданный слой, то есть наименьшее значение для такого, что . ${\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}$

Затем граф повторно выражается как серия орграфов , где каждый и где представляет собой сжатие всех предыдущих уровней в одну вершину. Поскольку каждый наклонный путь появляется не более чем в двух последовательных слоях и поскольку каждый из них образован двумя последовательными слоями, каждый наклонный путь появляется полностью как минимум в одном (и не более чем в двух последовательных таких графах). ${\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}}$

Для каждого определены три разделителя, которые при удалении разбивают граф на три компонента, каждая из которых содержит не более вершин оригинала. Поскольку каждый сепаратор состоит из двух слоев противоположных каналов, каждый сепаратор может состоять из двух каналов, всего до 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}$

Каждая вершина помечается, как указано выше, для каждого шага рекурсии, которая строит . Поскольку эта рекурсия имеет логарифмическую глубину, на каждую вершину сохраняется вся дополнительная информация. С этого момента запрос логарифмического времени на предмет достижимости так же прост, как поиск общего подходящего файла . Затем в исходной статье время запроса сокращается до 0,000 . ${\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)}$

Предварительная обработка выполняет следующие шаги. Мы добавляем новую вершину , у которой есть ребро к каждой вершине с нулевой степенью входа, и еще одну новую вершину с ребрами из каждой вершины с нулевой степенью выхода. Обратите внимание, что свойства позволяют нам сделать это, сохраняя планарность, то есть после этих сложений по-прежнему не будет пересечений ребер. Для каждой вершины мы сохраняем список смежностей (исходящих ребер) в порядке планарности графа (например, по часовой стрелке относительно вложения графа). Затем мы инициализируем счетчик и начинаем обход в глубину от . Во время этого обхода список смежности каждой вершины просматривается слева направо по мере необходимости. Когда вершины извлекаются из стека обхода, они помечаются значением и затем уменьшаются. Обратите внимание, что он всегда помечен значением и всегда помечен значком . Затем обход в глубину повторяется, но на этот раз список смежности каждой вершины просматривается справа налево. ${\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}}$

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

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

• гаммоидный
• ул - связность

Рекомендации

1. Скиена, Стивен С. (2011), «15.5 Транзитивное замыкание и сокращение», Руководство по разработке алгоритмов (2-е изд.), Springer, стр. 495–497, ISBN 9781848000698.
2. Кон, Пол Мориц (2003), Основная алгебра: группы, кольца и поля, Springer, стр. 17, ISBN 9781852335878.
3. Шмидт, Гюнтер (2010), Реляционная математика, Энциклопедия математики и ее приложений, том. 132, Издательство Кембриджского университета, стр. 132. 77, ISBN 9780521762687.
4. Герстинг, Джудит Л. (2006), Математические структуры для информатики (6-е изд.), Macmillan, p. 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. Хальфтермейер, Пьер, Связность в сетях и компактные схемы маркировки для планирования действий в чрезвычайных ситуациях, Университет Бордо..