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

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

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

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

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

Деревья и леса [ править ]

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

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

Отношение к связности вершин [ править ]

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

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

Графы без мостов [ править ]

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

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

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

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

Найти остовный лес из ${\ displaystyle G}$
Создание корневого леса из остовного дерева ${\ displaystyle F}$
Пройдите по лесу в предзаказе и пронумеруйте узлы. Родительские узлы в лесу теперь имеют меньшие номера, чем дочерние узлы. ${\ displaystyle F}$
Для каждого узла в предварительном заказе (обозначая каждый узел с использованием его номера предварительного заказа) выполните: ${\ displaystyle v}$
- Вычислите количество потомков леса для этого узла, добавив единицу к сумме потомков его потомков. ${\ Displaystyle ND (v)}$
- Вычислить , наименьшую метку предварительного порядка, доступную по пути, для которого все края, кроме последнего, остаются в поддереве с корнем . Это минимум набора, состоящего из метки предварительного порядка , значений дочерних узлов и меток предварительного порядка узлов, достижимых из ребер, которым не принадлежат . ${\ Displaystyle L (v)}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ Displaystyle L (ш)}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle 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-edge- и 2-вершины -соединение (которое распространяется на тесты связности с 3 ребрами и 3 вершинами в линейном времени).

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

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

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

Плацдарм [ править ]

Плацдармы моста, разделяющего области A и B в теории графов

Для связного графа мост может разделяться на область и область , то есть разрез . Вершины и являются двумя плацдармами и . ближний плацдарм и дальний плацдарм , и наоборот . $G$ $e$ $G$ $A$ $B$ $(A,B)$ $\alpha \in e\cap A$ $\beta \in e\cap B$ $A$ $B$ $\alpha$ $A$ $B$ $\beta$

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

Двусвязный компонент
Плацдарм
Вырезать (теория графов)

Заметки [ править ]

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

[1] Bollobás, Бел (1998), Современная теория графов , Graduate тексты по математике, 184 , Нью - Йорк: Springer-Verlag, стр. 6, DOI : 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 , МР 1154584 .

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

[4] Jaeger, F. (1985), "Обзор цикла накрытия гипотезы", Annals дискретной математики 27 - Циклы в графах , Северная Голландия Математика исследований, 27 , стр. 1-12, DOI : 10.1016 / S0304- 0208 (08) 72993-1.

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

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

[1]