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

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

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

Определение

Для ориентированного графа ${\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}$.^[1]

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

Алгоритмы

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

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

Затем граф повторно выражается в виде серии орграфов. ${\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-х подряд таких графиков)

Для каждого ${\displaystyle G_{i}}$, идентифицируются три разделителя, которые при удалении разбивают график на три компонента, каждая из которых содержит не более ${\displaystyle 1/2}$ вершины оригинала. Так как ${\displaystyle G_{i}}$ состоит из двух слоев противоположных погружных каналов, каждый сепаратор может состоять из до 2 погружных каналов, в общей сложности до 6 погружных каналов по всем сепараторам. Позволять ${\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-превосходить вершины появляются на одном и том же лицо (часто предполагается, что это внешняя грань), и можно разделить границу этой грани на две части, так что все вершины с нулевой степенью появляются на одной части, а все вершины с нулевой степенью - на другой (т. е. два типа вершин не чередуются).

Если ${\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)}$ время.

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

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

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

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

• Гаммоид
• ул-соединение

использованная литература

1. Скиена, Стивен С. (2011), «15.5 Transitive Closure and Reduction», Руководство по разработке алгоритмов (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, 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, Дои:10.1145/1039488.1039493, Г-Н  2145261, S2CID  18864647.
7. Камеда, Т. (1975), "О векторном представлении достижимости в плоских ориентированных графах", Письма об обработке информации, 3 (3): 75–77, Дои:10.1016/0020-0190(75)90019-8.
8. Деметреску, Камил; Торуп, Миккель; Чоудхури, Резаул Алам; Рамачандран, Виджая (2008), «Оракулы для расстояний, избегающих сбойного узла или соединения», SIAM Журнал по вычислениям, 37 (5): 1299–1318, CiteSeerX  10.1.1.329.5435, Дои:10.1137 / S0097539705429847, Г-Н  2386269.
9. Хальфтермейер, Пьер, Возможность подключения к сети и компактные схемы маркировки для аварийного планирования, Университет Бордо.