205
правок
Изменения
Нет описания правки
|statement = Определения (1), (2), (3) и (4) эквивалентны.
|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>(3) \Rightarrow (1)</tex> Пусть <tex>(a, b) = x</tex>. Пусть ребро <tex>x</tex> не является мостом по определению (1).
Тогда между вершинами <tex>a</tex> и <tex>b</tex> есть простой путь <tex>P = (a \rightsquigarrow b) : P \land x = \varnothing</tex>. Составим такой путь <tex>Q</tex>, что <tex>Q = ((u \rightsquigarrow w) </tex> o <tex> P) - x</tex>. Заметим, что он будет без разрывов. Сделаем путь <tex>Q</tex> простым (пройти по пути <tex>Q</tex>, удаляя все повторяющиеся вершины). Получим простой путь <tex>(u \rightsquigarrow w)</tex>, не проходящий по ребру <tex>x</tex>. Противоречие.
}}
== Литература ==
* Харари Ф. Теория графов.[http://reslib.com/book/985] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
== См.также ==
[[Точка сочленения, эквивалентные определения]]
