В теории графов , достижимость относится к способности , чтобы получить от одной вершины к другой в пределах графика. Вершина может достичь вершины (а также доступен из ), если существует последовательность смежных вершин (т.е. путь ), которая начинается с и заканчивается .
В неориентированном графе достижимость между всеми парами вершин может быть определена путем идентификации связанных компонентов графа. Любая пара вершин в таком графе может достигать друг друга тогда и только тогда, когда они принадлежат одной компоненте связности; следовательно, в таком графе достижимость симметрична ( достигает если только достигает ). Связные компоненты неориентированного графа могут быть идентифицированы за линейное время. Остальная часть статьи посвящена более сложной проблеме определения попарной достижимости в ориентированном графе (который, кстати, не обязательно должен быть симметричным).
Определение
Для ориентированного графа , с множеством вершин и набор кромок , Достижимости соотношение изявляется транзитивным замыканием из, то есть набор всех упорядоченных пар вершин в для которого существует последовательность вершин так что край в для всех . [1]
Если является ацикличным , то его отношение достижимости является частичным порядком ; любой частичный порядок может быть определен таким образом, например, как отношение достижимости его транзитивной редукции . [2] Примечательным следствием этого является то, что, поскольку частичные порядки антисимметричны, если может достигать , тогда мы знаем, что не может достичь. Интуитивно, если бы мы могли путешествовать из к и обратно к , тогда будет содержать цикл , противоречащий тому, что он ацикличен. Еслиявляется направленным, но не ациклическим (т.е. содержит хотя бы один цикл), то его отношение достижимости будет соответствовать предварительному порядку, а не частичному порядку. [3]
Алгоритмы
Алгоритмы определения достижимости делятся на два класса: те, которые требуют предварительной обработки, и те, которые не требуют .
Если у вас есть только один (или несколько) запросов, может быть более эффективным отказаться от использования более сложных структур данных и напрямую вычислить достижимость желаемой пары. Это может быть выполнено за линейное время с использованием таких алгоритмов, как поиск в ширину или итеративный поиск с углублением в глубину . [4]
Если вы будете делать много запросов, можно использовать более сложный метод; точный выбор метода зависит от характера анализируемого графа. В обмен на время предварительной обработки и дополнительное пространство для хранения мы можем создать структуру данных, которая затем сможет отвечать на запросы о достижимости для любой пары вершин всего завремя. Ниже описаны три различных алгоритма и структуры данных для трех различных, все более специализированных ситуаций.
Алгоритм Флойда-Уоршалла
Алгоритм Флойд-Воршалл [5] может быть использован для вычисления транзитивного замыкания любого ориентированного графа, что приводит к достижимости отношению , как в определении, выше.
Алгоритм требует время и пространство в худшем случае. Этот алгоритм заинтересован не только в достижимости, но и в вычислении кратчайшего пути между всеми парами вершин. Для графов, содержащих отрицательные циклы, кратчайшие пути могут быть не определены, но достижимость между парами все же может быть отмечена.
Алгоритм Торупа
Для плоских орграфов доступен гораздо более быстрый метод, как описано Миккелем Торупом в 2004 году. [6] Этот метод может отвечать на запросы о достижимости на плоском графе в время после траты время предварительной обработки для создания структуры данных размер. Этот алгоритм также может предоставить приблизительное расстояние кратчайшего пути, а также информацию о маршруте.
Общий подход состоит в том, чтобы связать с каждой вершиной относительно небольшой набор так называемых путей-разделителей, так что любой путь из вершины в любую другую вершину должен пройти хотя бы один из разделителей, связанных с или же . Схема разделов, связанных с достижимостью, приведена ниже.
Учитывая график , алгоритм начинается с организации вершин в слои, начиная с произвольной вершины . Слои строятся чередующимися шагами, сначала рассматривая все вершины, достижимые с предыдущего шага (начиная только с) , А затем все вершины , которые достигают к предыдущему шагу , пока все вершины не были отнесены к слою. При построении слоев каждая вершина появляется не более чем в двух слоях, и каждый направленный путь или угол наклона содержится в двух соседних слоях а также . Позволять быть последним созданным слоем, то есть наименьшим значением для такой, что .
Затем граф повторно выражается в виде серии орграфов. где каждый и где это сокращение всех предыдущих уровней в одну вершину. Потому что каждое погружение появляется не более чем в двух последовательных слоях, и потому что каждый образован двумя последовательными слоями, каждое погружение в появляется полностью по крайней мере в одном (и не более 2-х подряд таких графиков)
Для каждого , идентифицируются три разделителя, которые при удалении разбивают график на три компонента, каждая из которых содержит не более вершины оригинала. В видесостоит из двух слоев противоположных погружных каналов, каждый сепаратор может состоять из до 2 погружных каналов, в общей сложности до 6 погружных каналов по всем сепараторам. Позволятьбыть этим набором дипатов. Доказательство того, что такие разделители всегда можно найти, связано с теоремой о плоских разделителях Липтона и Тарьяна, и эти разделители могут быть расположены за линейное время.
Для каждого , направленный характер обеспечивает естественную индексацию его вершин от начала до конца пути. Для каждой вершины в , мы размещаем первую вершину в достижимый , а последняя вершина в что доходит до . То есть мы смотрим, насколько рано в мы можем получить от , и как долго мы можем оставаться в и все равно вернуться к . Эта информация хранится с каждым. Тогда для любой пары вершин а также , может достигать через если подключается к раньше чем подключается от .
Каждая вершина помечена, как указано выше, для каждого шага рекурсии, которая строит . Поскольку эта рекурсия имеет логарифмическую глубину, всегодополнительная информация сохраняется для каждой вершины. С этого момента запрос логарифмического времени для достижимости так же прост, как поиск по каждой паре меток общего, подходящего. Исходный документ затем работает над уменьшением времени запроса до.
Подводя итоги анализа этого метода, сначала учтите, что многоуровневый подход разбивает вершины так, чтобы каждая вершина рассматривалась только раз. Фаза разделения алгоритма разбивает граф на компоненты, которые не болееразмер исходного графа, что дает логарифмическую глубину рекурсии. На каждом уровне рекурсии требуется только линейная работа для определения разделителей, а также возможных связей между вершинами. Общий результат время предварительной обработки только дополнительная информация, хранящаяся для каждой вершины.
Алгоритм Камеды
Еще более быстрый метод предварительной обработки, предложенный Т. Камедой в 1975 г. [7], можно использовать, если граф является плоским , ациклическим , а также демонстрирует следующие дополнительные свойства: появляются все вершины с нулевой степенью и все вершины с нулевой степенью на одной и той же грани (часто предполагается, что это внешняя грань), и можно разделить границу этой грани на две части, так что все вершины с нулевой степенью появляются на одной части, а все вершины с нулевой степенью появляются на другой (т.е. два типа вершин не чередуются).
Если проявляет эти свойства, тогда мы можем предварительно обработать график только за время и только хранить дополнительные биты на вершину, отвечая на запросы о достижимости для любой пары вершин в время с простым сравнением.
Предварительная обработка выполняет следующие шаги. Добавляем новую вершину у которого есть ребро к каждой вершине с нулевой степенью, и еще одна новая вершина с ребрами из каждой вершины с нулевой степенью выхода. Обратите внимание, что свойствапозволяют сделать это с сохранением планарности, то есть после этих добавлений не будет пересечений краев. Для каждой вершины мы храним список смежностей (внешних ребер) в порядке планарности графа (например, по часовой стрелке относительно вложения графа). Затем мы инициализируем счетчик и начать обход в глубину с . Во время этого обхода список смежности каждой вершины просматривается слева направо по мере необходимости. Когда вершины извлекаются из стека обхода, они помечаются значением, а также затем уменьшается. Обратите внимание, что всегда обозначается значением а также всегда помечен . Затем повторяется обход в глубину, но на этот раз список смежности каждой вершины просматривается справа налево.
По завершении а также , и их инцидентные края, удаляются. Каждая оставшаяся вершина хранит двумерную метку со значениями из к . Учитывая две вершины а также , и их ярлыки а также мы говорим, что если и только если , , и существует хотя бы один компонент или же что строго меньше, чем или же , соответственно.
Главный результат этого метода состоит в том, что доступен из если и только если , который легко вычисляется в время.
Связанные проблемы
Связанная с этим проблема - решить запросы о достижимости с некоторым числом. вершинных отказов. Например: «Может вершина все еще дойти до вершины хотя вершины потерпели неудачу и больше не могут быть использованы? »Подобная проблема может относиться к сбоям ребер, а не к сбоям вершин, или их сочетанию. Методика поиска в ширину работает так же хорошо для таких запросов, но создание эффективного оракула более сложно. [8] [9]
Другая проблема, связанная с запросами о достижимости, заключается в быстром пересчете изменений в отношениях достижимости при изменении некоторой части графа. Например, это актуальная проблема для сборки мусора, которая должна сбалансировать восстановление памяти (чтобы ее можно было перераспределить) с проблемами производительности работающего приложения.
Смотрите также
Рекомендации
- ^ Skiena, Стивен С. (2011), "15,5 Переходная Закрытие и сокращение", Алгоритм Руководство по проектированию (2 - е изд.), М., стр. 495-497, ISBN 9781848000698.
- ^ Кон, Пол Мориц (2003), Базовая алгебра: группы, кольца и поля , Springer, стр. 17, ISBN 9781852335878.
- ^ Шмидт, Гюнтер (2010), Реляционная математика , Энциклопедия математики и ее приложений, 132 , Cambridge University Press, стр. 77, ISBN 9780521762687.
- ^ Герстинг, Джудит Л. (2006), Математические структуры для компьютерных наук (6-е изд.), Macmillan, стр. 519, ISBN 9780716768647.
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), «Транзитивное замыкание ориентированного графа», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 632–634, ISBN 0-262-03293-7.
- ^ Thorup, Миккель (2004), "Компактные оракулы для достижимости и приближенных расстояний в плоских орграфах", Журнал ACM , 51 (6): 993-1024, DOI : 10,1145 / 1039488,1039493 , МР 2145261 , S2CID 18864647.
- ^ Камеда, Т. (1975), "О векторном представлении достижимости в плоских ориентированных графах", Письма об обработке информации , 3 (3): 75–77, DOI : 10.1016 / 0020-0190 (75) 90019-8.
- ^ Деметреску, Камил; Thorup, Mikkel ; Чоудхури, Резаул Алам; Рамачандрана, Виджая (2008), "Оракулы для расстояний избегая неисправного узла или ссылку", SIAM журнал по вычислениям , 37 (5): 1299-1318, CiteSeerX 10.1.1.329.5435 , DOI : 10,1137 / S0097539705429847 , МР 2386269.
- ^ Хальфтермайер, Пьер, Возможность подключения к сетям и компактные схемы маркировки для аварийного планирования , Университет Бордо.