Изменения

Пусть <mathtex> G </mathtex> {{- --}} связный граф.

'''Мост''' ''(1англ. bridge) Мост '' графа <mathtex>G</mathtex> {{--- }} ребро, соединяющее как минимум две компоненты [[Отношение рёберной двусвязности|реберной двусвязности ]] <mathtex>G</mathtex>. <tex>(1)</tex>

(2) Мост графа <mathtex>G</mathtex> {{- --}} ребро, при удалении которого граф <mathtex>G</mathtex> становится несвязным. <tex>(2)</tex>

(3) Ребро <mathtex>x</mathtex> является мостом графа <mathtex>G</mathtex>, если в <mathtex>G</mathtex> существуют такие вершины <mathtex>u</mathtex> и <mathtex>v</mathtex>, что любой простой путь между этими вершинами проходит через ребро <mathtex>x.</mathtex> <tex>(3)</tex>

(4) Ребро <mathtex>x</mathtex> является мостом графа <mathtex>G</mathtex>, если существует разбиение множества вершин <mathtex>V</mathtex> на такие множества <mathtex>U</mathtex> и <mathtex>W</mathtex>, что <mathtex>\forall u \in U</mathtex> и <mathtex>\forall w \in W</mathtex> ребро <mathtex>x</mathtex> принадлежит любому простому пути <mathtex>u \rightsquigarrow w</mathtex>. <tex>(4)</tex>

<mathtex>(21) \Rightarrow (42)</mathtex> В условиях определения (4) пусть существует такие Пусть ребро <tex>x</tex> соединяет вершины <mathtex>ua</mathtex> и <mathtex>wb</mathtex>, что . Пусть граф <tex> G - {x} </tex> {{---}} связный. Тогда между ними вершинами <tex>a</tex> и <tex>b</tex> существует простой еще один путь , т.е. между вершинами <mathtex>P: x \notin Pa</tex> и <tex>b</mathtex>существуют два реберно-непересекающихся пути. Но тогда граф ребро <tex>x</tex> не является мостом графа <mathtex>G - {x}</mathtex> - связный. Противоречие.

<mathtex>(42) \Rightarrow (34)</mathtex> Возьмем В условиях определения (4) пусть существуют такие вершины <mathtex>\forall u \in U</mathtex> и <mathtex>\forall w \in W </math>. Тогда <math>\forall</mathtex> , что между ними существует простой путь <mathtex>u P: x \rightsquigarrow wnotin P</mathtex> содержит ребро . Но тогда граф <mathtex>G - {x}</mathtex>{{---}} связный. Противоречие. Утверждение доказано

<mathtex>(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>. Утверждение доказано <tex>(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 с.) [[Категория:Алгоритмы и структуры данных]][[Категория:Связность в графах]]