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

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

Если является ациклическим , то его отношение достижимости является частичным порядком ; любой частичный порядок может быть определен таким образом, например, как отношение достижимости его транзитивной редукции . ^[2] Примечательным следствием этого является то, что, поскольку частичные порядки антисимметричны, если можно достичь , то мы знаем, что достичь невозможно . Интуитивно, если бы мы могли путешествовать от туда и обратно , тогда мы бы содержали цикл , что противоречит его ацикличности. Если направлено, но не${\ displaystyle G}$${\ 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 О (п \ журнал {п})}$${\ Displaystyle О (п \ журнал {п})}$

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

Алгоритм Камеды [ править ]

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

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

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

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

См. Также [ править ]

• Гаммоид
• st -соединение

Ссылки [ править ]