Мост, эквивалентные определения — различия между версиями
| Строка 30: | Строка 30: | ||
<math>(3) \Rightarrow (1)</math> Пусть <math>(a, b) = x</math>. Пусть ребро <math>x</math> не является мостом по определению (1). | <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>a</math> и <math>b</math> есть простой путь <math>P = (a \rightsquigarrow b) : 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>. Противоречие. |
}} | }} | ||
== См.также == | == См.также == | ||
[[Точка сочленения, эквивалентные определения]] | [[Точка сочленения, эквивалентные определения]] | ||
Версия 05:30, 8 октября 2010
Пусть - связный граф.
| Определение: |
| (1) Мост графа - ребро, соединяющее как минимум две компоненты реберной двусвязности . |
| Определение: |
| (2) Мост графа - ребро, при удалении которого граф становится несвязным. |
| Определение: |
| (3) Ребро является мостом графа , если в существуют такие вершины и , что любой простой путь между этими вершинами проходит через ребро |
| Определение: |
| (4) Ребро является мостом графа , если существует разбиение множества вершин на такие множества и , что и ребро принадлежит любому простому пути |
| Теорема: |
Определения (1), (2), (3) и (4) эквивалентны. |
| Доказательство: |
|
Пусть ребро соединяет вершины и . Пусть граф - связный. Тогда между вершинами и существует еще один путь, т.е. между вершинами и существуют два реберно неперескающихся пути. Но тогда ребро не является мостом графа . Противоречие. В условиях определения (4) пусть существует такие вершины и , что между ними существует простой путь . Но тогда граф - связный. Противоречие. Возьмем и . Тогда простой путь содержит ребро . Утверждение доказано Пусть . Пусть ребро не является мостом по определению (1). Тогда между вершинами и есть простой путь . Составим такой путь , что . Заметим, что он будет без разрывов. Сделаем путь простым (пройти по пути , удаляя все повторяющиеся вершины). Получим простой путь , не проходящий по ребру . Противоречие. |
