Мост (теория графов)

Ребро в графе связей узлов, удаление которого приведет к отключению графа

Граф с 16 вершинами и шестью мостами (выделены красным)

Неориентированный связный граф без ребер-мостов.

В теории графов мост , перешеек , разрезанное ребро или разрезанная дуга — это ребро графа , удаление которого увеличивает количество связных компонентов графа . ^[1] Эквивалентно, ребро является мостом тогда и только тогда, когда оно не содержится ни в одном цикле . Для связного графа мост может однозначно определить разрез . Граф называется бесмостовым или бесперешечным, если он не содержит мостов.

Этот тип моста следует отличать от несвязанного значения слова «мост» в теории графов, подграфа, отделенного от остальной части графа указанным подмножеством вершин; см. мост .

Деревья и леса

Граф с узлами может содержать не более мостов, поскольку добавление дополнительных ребер должно создавать цикл. Графы, в которых есть ровно мосты, являются в точности деревьями , а графы, в которых каждое ребро является мостом, являются в точности лесами . ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$

В каждом неориентированном графе на вершинах существует отношение эквивалентности , согласно которому две вершины связаны друг с другом всякий раз, когда их соединяют два непересекающихся по ребрам пути. (Каждая вершина связана сама с собой двумя путями нулевой длины, которые идентичны, но, тем не менее, не пересекаются по ребрам.) Классы эквивалентности этого отношения называются компонентами 2-реберной связности , а мосты графа — это в точности те ребра, у которых конечные точки принадлежат разным компонентам. Дерево мост-блок графа имеет вершину для каждого нетривиального компонента и ребро для каждого моста. ^[2]

Связь со связностью вершин

Мосты тесно связаны с концепцией вершин сочленения , вершин, которые принадлежат каждому пути между некоторой парой других вершин. Две конечные точки моста являются вершинами сочленения, если они не имеют степени 1, хотя ребро, не являющееся мостом, также может иметь две вершины сочленения в качестве конечных точек. Аналогично тому, как графы без мостов являются 2-реберно-связными, графы без вершин сочленения являются 2-вершинно-связными .

В кубическом графе каждая разрезанная вершина является конечной точкой хотя бы одного моста.

Бесмостовые графики

Граф без мостов — это граф, не имеющий мостов. Эквивалентные условия заключаются в том, что каждый связный компонент графа имеет разложение с открытым ухом , ^[3] что каждый связный компонент является 2-реберно-связным или (по теореме Роббинса ), что каждый связный компонент имеет сильную ориентацию . ^[3]

Важной открытой проблемой, связанной с мостами, является гипотеза о двойном покрытии цикла , выдвинутая Сеймуром и Секересом (1978 и 1979, независимо), которая утверждает, что каждый граф без мостов допускает мультимножество простых циклов, которое содержит каждое ребро ровно дважды. ^[4]

Алгоритм поиска мостов Тарьяна

Первый алгоритм поиска мостов в графе с линейным временем (линейный по числу ребер) был описан Робертом Тарджаном в 1974 году. ^[5] Он выполняет следующие шаги:

• Найдите охватывающий лес ${\displaystyle G}$
• Создание корневого леса из связующего леса ${\displaystyle F}$
• Пройдите лес в предварительном порядке и пронумеруйте узлы. Родительские узлы в лесу теперь имеют меньшее количество, чем дочерние узлы. ${\displaystyle F}$
• Для каждого узла в предварительном заказе (обозначая каждый узел его номером предварительного заказа) выполните: ${\displaystyle v}$
  • Вычислите количество потомков леса для этого узла, добавив единицу к сумме его дочерних потомков. ${\displaystyle ND(v)}$
  • Compute — наименьшая метка предварительного порядка, достижимая по пути, для которого все ребра, кроме последнего, остаются внутри поддерева с корнем в . Это минимум набора, состоящего из метки предварительного порядка , значений в дочерних узлах и меток предварительного порядка узлов, достижимых по ребрам, которые не принадлежат . ${\displaystyle L(v)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle L(w)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle F}$
  • Аналогичным образом вычислите самую высокую метку предварительного порядка, доступную для пути, для которого все ребра, кроме последнего, остаются внутри поддерева с корнем в . Это максимум набора, состоящего из метки предварительного порядка , значений в дочерних узлах и меток предварительного порядка узлов, достижимых из ребер, которые не принадлежат . ${\displaystyle H(v)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle H(w)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle F}$
  • Для каждого узла с родительским узлом if и then ребро от to является мостом. ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle L(w)=w}$ ${\displaystyle H(w)<w+ND(w)}$ ${\displaystyle v}$ ${\displaystyle w}$

Поиск мостов с помощью цепных разложений

Очень простой алгоритм поиска мостов ^[6] использует цепную декомпозицию . Цепная декомпозиция не только позволяет вычислить все мосты графа, но также позволяет считывать каждую вырезанную вершину графа G (и дерево блочного разреза графа G ), предоставляя общую основу для тестирования 2-реберных и 2-вершинных -связность (которая распространяется на тесты на связность трех ребер и трех вершин за линейное время).

Цепные разложения представляют собой специальные ушные разложения, зависящие от DFS-дерева T группы G , и их можно вычислить очень просто: пусть каждая вершина будет помечена как непосещенная. Для каждой вершины v в возрастающих DFS- номера 1... n пройдите каждое обратное ребро (т. е. каждое ребро, не входящее в дерево DFS), инцидентное v , и следуйте по пути ребер дерева обратно к корню T , останавливаясь в точке первая вершина, помеченная как посещенная. При таком обходе каждая пройденная вершина помечается как посещенная. Таким образом, обход останавливается самое позднее на v и образует либо направленный путь, либо цикл, начиная с v; мы называем этот путь или цикл цепочкой . i- я цепь, найденная с помощью этой процедуры, называется C _i . C=C ₁ ,C ₂ ,... тогда является цепным разложением G .

Следующие характеристики затем позволяют эффективно считывать некоторые свойства G из C , включая все мосты G . ^[6] Пусть C — цепное разложение простого связного графа G=(V,E) .

1. G 2-реберно связна тогда и только тогда, когда цепи из C разбивают E .
2. Ребро e в G является мостом тогда и только тогда, когда e не содержится ни в одной цепи из C .
3. Если G 2-реберно связен, C — ушное разложение .
4. G является 2-вершинно связным тогда и только тогда, когда G имеет минимальную степень 2 и C ₁ — единственный цикл в C .
5. Вершина v в 2-реберно-связном графе G является разрезной вершиной тогда и только тогда, когда v является первой вершиной цикла в C - C ₁ .
6. Если G 2-вершинно связен, C — разложение с открытым ухом .

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

• Двусвязный компонент
• Cut (теория графов)

Примечания

1. Боллобас, Бела (1998), Современная теория графов, Тексты для выпускников по математике, том. 184, Нью-Йорк: Springer-Verlag, с. 6, номер домена : 10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, МР  1633290.
2. Уэстбрук, Джеффри ; Тарьян, Роберт Э. (1992), «Поддержание в режиме онлайн мостовых и двусвязных компонентов», Algorithmica , 7 (5–6): 433–464, doi : 10.1007/BF01758773, MR  1154584.
3. Роббинс, HE (1939), «Теорема о графах с применением к проблеме управления дорожным движением», The American Mathematical Monthly , 46 : 281–283, doi : 10.2307/2303897, hdl : 10338.dmlcz/101517.
4. Джагер, Ф. (1985), «Обзор гипотезы о двойном покрытии цикла», Анналы дискретной математики 27 – Циклы в графиках , Математические исследования Северной Голландии, том. 27, стр. 1–12, номер документа : 10.1016/S0304-0208(08)72993-1..
5. Тарьян, Р. Эндре (1974), «Заметка о поиске мостов графа», Information Processing Letters , 2 (6): 160–161, doi : 10.1016/0020-0190(74)90003-9, MR  0349483.
6. Шмидт, Йенс М. (2013), «Простой тест на связность 2 вершин и 2 ребер», Information Processing Letters , 113 (7): 241–244, arXiv : 1209.0700 , doi : 10.1016/j .ipl.2013.01.016.