Изменения
→Эквивалентные определения
Пусть <mathtex> G </mathtex> {{- --}} связный граф.
{{Определение
|definition=
'''Мост''' ''(1англ. bridge) Мост '' графа <mathtex>G</mathtex> {{- --}} ребро, соединяющее как минимум две компоненты реберной двусвязности <mathtex>G</mathtex>. <tex>(1)</tex>
}}
[[Файл:Bridge_1.png|left|thumb|240px|Граф <tex>G</tex>]]
<br clear="all"/>
Пример графа с тремя мостами
==Эквивалентные определения==
{{Определение
|definition=
}}
{{Определение
|definition=
}}
{{Определение
|definition=
}}
|statement = Определения (1), (2), (3) и (4) эквивалентны.
|proof =
<mathtex>(1) \Rightarrow (2)</tex> Пусть ребро <tex>x</tex> соединяет вершины <tex>a</tex> и <tex>b</tex>. Пусть граф <tex> G - {x} </tex> {{---}} связный. Тогда между вершинами <tex>a</tex> и <tex>b</tex> существует еще один путь, т.е. между вершинами <tex>a</tex> и <tex>b</tex> существуют два реберно-непересекающихся пути. Но тогда ребро <tex>x</tex> не является мостом графа <tex>G</tex>. Противоречие. <tex>(2) \Rightarrow (4)</mathtex> В условиях определения (4) пусть существует существуют такие вершины <mathtex>u</mathtex> и <mathtex>w</mathtex>, что между ними существует простой путь <mathtex>P: x \notin P</mathtex>. Но тогда граф <mathtex>G - {x}</mathtex> {{--- }} связный. Противоречие.
<mathtex>(4) \Rightarrow (3)</mathtex> Возьмем <mathtex>\forall u \in U</mathtex> и <mathtex>\forall w \in W </mathtex>. Тогда <mathtex>\forall</mathtex> простой путь <mathtex>u \rightsquigarrow w</mathtex> содержит ребро <mathtex>x</mathtex>. Утверждение доказано
<mathtex>(3) \Rightarrow (1)</mathtex> Пусть <mathtex>(a, b) = x</mathtex>. Пусть ребро <mathtex>x</mathtex> не является мостом по определению (1).Тогда между вершинами <mathtex>a</mathtex> и <mathtex>b</mathtex> есть простой путь <mathtex>P : P \and cap x = \varnothing</mathtex>. Составим такой путь <mathtex>Q</mathtex>, что <mathtex>Q = ((u \rightsquigarrow wa ) \or circ P\circ (b \rightsquigarrow w)) - x</mathtex>. Заметим, что он будет без разрывов. Сделаем путь <mathtex>Q</mathtex> [[Теорема о существовании простого пути в случае существования пути|простым (пройти по пути <math>Q</math>, удаляя все повторяющиеся вершины)]]. Получим простой путь <mathtex>(u \rightsquigarrow w)</mathtex>, не проходящий по ребру <mathtex>x</mathtex>. Противоречие.
}}
== См.также ==
* [[Точка сочленения, эквивалентные определения]]
==Источники информации==
* Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Связность в графах]]