Доступность

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

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

Определение

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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