Изменения
Добавил ссылку на статью "Использование обхода в глубину для поиска мостов"
{{Определение
|definition=
'''Мост''' ''(англ. bridge)'' графа <tex>G</tex> {{---}} ребро, соединяющее две компоненты [[Отношение рёберной двусвязности|реберной двусвязности ]] <tex>G</tex>. <tex>(1)</tex>
}}
<tex>(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)</tex> В условиях определения (4) пусть существует существуют такие вершины <tex>u</tex> и <tex>w</tex>, что между ними существует простой путь <tex>P: x \notin P</tex>. Но тогда граф <tex>G - {x}</tex> {{---}} связный. Противоречие.
<tex>(4) \Rightarrow (3)</tex> Возьмем <tex>\forall u \in U</tex> и <tex>\forall w \in W </tex>. Тогда <tex>\forall</tex> простой путь <tex>u \rightsquigarrow w</tex> содержит ребро <tex>x</tex>. Утверждение доказано
== См.также ==
* [[Точка сочленения, эквивалентные определения]]
* [[Использование обхода в глубину для поиска мостов]]
==Источники информации==
