Изменения

Перейти к: навигация, поиск

Мост, эквивалентные определения

36 байт добавлено, 09:32, 6 февраля 2012
Нет описания правки
Пусть <tex> G </tex> {{- --}} связный граф.
{{Определение
|definition=
(1) '''Мост ''' графа <tex>G</tex> {{- --}} ребро, соединяющее две компоненты реберной двусвязности <tex>G</tex>.
}}
[[Файл:Bridge.png]]
{{Определение
|definition=
(2) Мост графа <tex>G</tex> {{- --}} ребро, при удалении которого граф <tex>G</tex> становится несвязным.
}}
|proof =
<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>. Утверждение доказано
322
правки

Навигация