205
правок
Изменения
Нет описания правки
Пусть <math> G </math> - связный граф.
{{Определение
|definition=
{{Определение
|definition=
(2) Мост графа <math>G</math> - ребро, при удалении которого в граф <math>G</math> увеличивается число компонент связностистановится несвязным.
}}
|statement = Определения (1), (2), (3) и (4) эквивалентны.
|proof =
<math>(1) \Rightarrow (2)</math> Пусть ребро <math>x</math> соединяет вершины <math>a</math> и <math>b</math>. Пусть граф <math> G - {x} </math> - связный. Тогда между вершинами <math>a</math> и <math>b</math> существует еще один путь, т.е. между вершинами <math>a</math> и <math>b</math> существуют два реберно неперескающихся пути. Но тогда ребро <math>x</math> не является мостом графа <math>G</math>. Противоречие.
}}
