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

Пусть [math] G [/math] - связный граф.

Определение:

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

Определение:

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

Определение:

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

Определение:

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

Теорема:

Определения (1), (2), (3) и (4) эквивалентны.

Доказательство:

[math]\triangleright[/math]

[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]. Противоречие. [math](2) \Rightarrow (4)[/math] В условиях определения (4) пусть существует такие вершины [math]u[/math] и [math]w[/math], что между ними существует простой путь [math]P: x \notin P[/math]. Но тогда граф [math]G - {x}[/math] - связный. Противоречие. [math](4) \Rightarrow (3)[/math] Возьмем [math]\forall u \in U[/math] и [math]\forall w \in W [/math]. Тогда [math]\forall[/math] простой путь [math]u \rightsquigarrow w[/math] содержит ребро [math]x[/math]. Утверждение доказано [math](3) \Rightarrow (1)[/math] Пусть [math](a, b) = x[/math]. Пусть ребро [math]x[/math] не является мостом по определению (1). Тогда между вершинами [math]a[/math] и [math]b[/math] есть простой путь [math]P : P \and x = \varnothing[/math]. Составим такой путь [math]Q[/math], что [math]Q = ((u \rightsquigarrow w) \or P) - x[/math]. Заметим, что он будет без разрывов. Сделаем путь [math]Q[/math] простым (пройти по пути [math]Q[/math], удаляя все повторяющиеся вершины). Получим простой путь [math](u \rightsquigarrow w)[/math], не проходящий по ребру [math]x[/math]. Противоречие.

[math]\triangleleft[/math]

См.также

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