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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

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

[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 .

[robbins39-3] Jump up to: ^а ^б Роббинс, HE (1939), «Теорема о графах с применением к проблеме управления дорожным движением», The American Mathematical Monthly , 46 (5): 281–283, doi : 10.2307/2303897 , hdl : 10338.dmlcz/ 101517 , JSTOR 2303897 .

[4] Джагер, Ф. (1985), «Обзор гипотезы о двойном покрытии цикла», Annals of Discrete Mathematics 27 – Cycles in Graphs , North-Holland Mathematics Studies, vol. 27, стр. 1–12, doi : 10.1016/S0304-0208(08)72993-1 , ISBN. 978-0-444-87803-8 .

[5] Тарьян, Р. Эндре (1974), «Заметки о поиске мостов графа», Information Processing Letters , 2 (6): 160–161, doi : 10.1016/0020-0190(74)90003-9 , MR 0349483 .

[Schmidt-6] Jump up to: ^а ^б Шмидт, Йенс М. (2013), «Простой тест на связность 2 вершин и 2 ребер», Information Processing Letters , 113 (7): 241–244, arXiv : 1209.0700 , doi : 10.1016/j.ipl .2013.01.016 .

[1]

[2]

[3]

[4]

[5]

[6]