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

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

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

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

• 1 Определение
• 2 Алгоритмы
  • 2.1 Алгоритм Флойда-Уоршалла
  • 2.2 Алгоритм Торупа
  • 2.3 Алгоритм Камеды
• 3 Связанные проблемы
• 4 См. Также
• 5 Ссылки

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

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

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

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

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

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

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

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

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

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

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

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

Затем график повторно выражается в виде серии орграфов $G\; 0,\; G\; 1,\dots ,\; G\; k\; -\; 1\; \{\backslash \; displaystyle\; G\_\; \{0\},\; G\_\; \{1\},\; \backslash \; ldots,\; G\_\; \{k-1\}\}$, где каждый $G\; i\; =\; ri\; \cup \; L\; я\; \cup \; L\; я\; +\; 1\; \{\backslash \; displaystyle\; G\_\; \{i\}\; =\; r\_\; \{i\}\; \backslash \; cup\; L\_\; \{i\}\; \backslash \; cup\; L\_\; \{i\; +\; 1\}\}$и где $ri\; \{\backslash \; displaystyle\; r\_\; \{\; i\}\}$- сокращение всех предыдущих уровней $L\; 0\dots \; L\; i\; -\; 1\; \{\backslash \; displaystyle\; L\_\; \{0\}\; \backslash \; ldots\; L\_\; \{i-1\}\}$в единственная вершина. Поскольку каждый погружной путь появляется не более чем в двух последовательных слоях, и поскольку каждый $G\; i\; \{\backslash \; displaystyle\; G\_\; \{i\}\}$образован двумя последовательными слоями, каждый погруженный путь в $G\; \{\backslash \; displaystyle\; G\}$целиком появляется по крайней мере в одном $G\; i\; \{\backslash \; displaystyle\; G\_\; \{i\}\}$(и не более чем в двух последовательных таких графиках)

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

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

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

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

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

Подходящий орграф для метода Камеды с добавлением $s\; \{\backslash \; displaystyle\; s\}$и $t\; \{\backslash \; displaystyle\; t\}$ Тот же график, что и выше, после запуска алгоритма Камеды, показывающий метки DFS для каждой вершины

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

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

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

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

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

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

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

• Gammoid
• st-connectivity