Изменения

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

(1) Мост графа <mathtex>G</mathtex> - ребро, соединяющее как минимум две компоненты реберной двусвязности <mathtex>G</mathtex>.

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

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

(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>

<mathtex>(1) \Rightarrow (2)</mathtex> Пусть ребро <mathtex>x</mathtex> соединяет вершины <mathtex>a</mathtex> и <mathtex>b</mathtex>. Пусть граф <mathtex> G - {x} </mathtex> - связный. Тогда между вершинами <mathtex>a</mathtex> и <mathtex>b</mathtex> существует еще один путь, т.е. между вершинами <mathtex>a</mathtex> и <mathtex>b</mathtex> существуют два реберно не пересекающихся пути. Но тогда ребро <mathtex>x</mathtex> не является мостом графа <mathtex>G</mathtex>. Противоречие.

<mathtex>(2) \Rightarrow (4)</mathtex> В условиях определения (4) пусть существует такие вершины <mathtex>u</mathtex> и <mathtex>w</mathtex>, что между ними существует простой путь <mathtex>P: x \notin P</mathtex>. Но тогда граф <mathtex>G - {x}</mathtex> - связный. Противоречие.

<mathtex>(4) \Rightarrow (3)</mathtex> Возьмем <mathtex>\forall u \in U</mathtex> и <mathtex>\forall w \in W </mathtex>. Тогда <mathtex>\forall</mathtex> простой путь <mathtex>u \rightsquigarrow w</mathtex> содержит ребро <mathtex>x</mathtex>. Утверждение доказано

<mathtex>(3) \Rightarrow (1)</mathtex> Пусть <mathtex>(a, b) = x</mathtex>. Пусть ребро <mathtex>x</mathtex> не является мостом по определению (1).Тогда между вершинами <mathtex>a</mathtex> и <mathtex>b</mathtex> есть простой путь <mathtex>P = (a \rightsquigarrow b) : P \and land x = \varnothing</mathtex>. Составим такой путь <mathtex>Q</mathtex>, что <mathtex>Q = ((u \rightsquigarrow w) \or lor P) - x</mathtex>. Заметим, что он будет без разрывов. Сделаем путь <mathtex>Q</mathtex> простым (пройти по пути <mathtex>Q</mathtex>, удаляя все повторяющиеся вершины). Получим простой путь <mathtex>(u \rightsquigarrow w)</mathtex>, не проходящий по ребру <mathtex>x</mathtex>. Противоречие.