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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф с 6 мостами (выделены красным)
Неориентированный связный граф, не имеющий разрезающих рёбер

В теории графов мостом называется ребро, удаление которого увеличивает число компонент связности.[1] Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки). Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.

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

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

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

Связь с вершинной связностью[править | править вики-текст]

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

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

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

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

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

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

Первый алгоритм для нахождения мостов в графе, имеющий линейное время работы, был описан Робертом Тарьяном в 1974.[5] Алгоритм работает следующим образом:

  • Находим остовный лес графа G
  • Создаём лес с корнями F из остовного дерева
  • Обходим лес F в прямом порядке[en] и нумеруем вершины. Родительские вершины теперь имеют меньшие номера по сравнению с потомками.

Будем обозначать ребро (v,w), содержащееся в дереве, как v\to w , а не содержащееся — как v--w.

  • Для каждой вершины v при прямом обходе выполняем:
    • Вычисляем число потомков ND(v) для вершины, добавляя единицу при переходе к следующей вершине (включая вершину v).

ND(v) = 1 + \sum_{v \to w} ND(w).

    • Вычисляем L(v), минимальный номер, до которого можно дойти из вершины v, идя по рёбрам поддерева, начинающегося в v (за исключением последнего ребра). Это минимальный номер в множестве, состоящем из значений L(w) потомков вершины v и номеров вершин, до которых можно дойти из v по рёбрам, не принадлежащим F.

L(v) = \min(\{v\} \cup \{L(v) \mid v \to w\} \cup \{w \mid v--w\})

    • Аналогичным образом вычислим H(v), наибольший номер, до которого можно добраться, идя по рёбрам поддерева, начинающегося v. Это максимальный номер в множестве значений, состоящем из значений H(w) потомков вершины v и номеров вершин, до которых можно дойти из v по рёбрам, не принадлежащим F.

H(v) = \max(\{v\} \cup \{H(v) \mid v \to w\} \cup \{w \mid v--w\})

    • Для каждой вершины w с родителем v проверяем, если L(w) = w и H(w) <  w + ND(w), то ребро из v в w является мостом.

Если v\to w — мост, то ясно, что из поддерева с корнем в w не должно быть возможности выйти на вершину, не принадлежащую этому поддереву. Для проверки этого достаточно проверить L(w),H(w) — условие L(w) = w означает, что мы не выйдем на вершину, лежащую ближе к корню, а условие H(w) <  w + ND(w) — что мы не выйдем на другое поддерево.

Поиск мостов с помощью разложения на цепочки[править | править вики-текст]

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

Разложение на цепочки — это специальный случай разложения на уши, основанный на поиске в глубину по дереву T графа G и оно может быть выполнено очень просто:

Пусть все вершины помечены как непосещённые. Для всех вершин v в восходящем порядке номеров обхода 1...n, проходим каждое обратное ребро (то есть ребро, не принадлежащее дереву обхода), инцидентное вершине v, и проследуем по рёбрам дерева к корню пока не встретим посещённую вершину. Во время этого прохода помечаем все пройденные вершины как посещённые. Этот проход закончится образованием либо пути, либо цикла, начинающегося в v, мы назовём это путь или цикл цепочкой. Будем обозначать i-ю цепочку, полученную такой процедурой, как Ci. C=C1,C2,... является тогда разбиением графа G на цепочки.

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

Пусть C — разложение на цепочки простого связного графа G=(V,E).

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

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

  1. Béla Bollobás Modern Graph Theory. — New York: Springer-Verlag, 1998. — Т. 184. — С. 6. — (Graduate Texts in Mathematics). — ISBN 0-387-98488-7. — DOI:10.1007/978-1-4612-0619-4.
  2. Jeffery Westbrook, Robert E. Tarjan Maintaining bridge-connected and biconnected components on-line // Algorithmica. — 1992. — В. 5-6. — Т. 7. — С. 433–464. — DOI:10.1007/BF01758773.
  3. 1 2 H. E. Robbins A theorem on graphs, with an application to a problem of traffic control // The American Mathematical Monthly. — 1939. — Т. 46. — С. 281–283..
  4. F. Jaeger Annals of Discrete Mathematics 27 – Cycles in Graphs. — 1985. — Т. 27. — С. 1–12. — (North-Holland Mathematics Studies). — DOI:10.1016/S0304-0208(08)72993-1.
  5. R. Endre Tarjan A note on finding the bridges of a graph // Information Processing Letters. — В. 6. — Т. 2. — С. 160–161. — DOI:10.1016/0020-0190(74)90003-9.
  6. 1 2 Jens M. Schmidt A Simple Test on 2-Vertex- and 2-Edge-Connectivity // Information Processing Letters. — 2013. — В. 7. — Т. 113. — С. 241–244. — DOI:10.1016/j.ipl.2013.01.016.