Мост, эквивалентные определения — различия между версиями
| Строка 23: | Строка 23: | ||
|statement = Определения (1), (2), (3) и (4) эквивалентны. | |statement = Определения (1), (2), (3) и (4) эквивалентны. | ||
|proof = | |proof = | ||
| − | <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>(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>(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 v</math> содержит ребро <math>x</math>. Утверждение доказано | ||
}} | }} | ||
Версия 03:58, 8 октября 2010
Пусть - связный граф.
| Определение: |
| (1) Мост графа - ребро, соединяющее как минимум две компоненты реберной двусвязности . |
| Определение: |
| (2) Мост графа - ребро, при удалении которого граф становится несвязным. |
| Определение: |
| (3) Ребро является мостом графа , если в существуют такие вершины и , что любой простой путь между этими вершинами проходит через ребро |
| Определение: |
| (4) Ребро является мостом графа , если существует разбиение множества вершин на такие множества и , что и ребро принадлежит любому простому пути |
| Теорема: |
Определения (1), (2), (3) и (4) эквивалентны. |
| Доказательство: |
|
Пусть ребро соединяет вершины и . Пусть граф - связный. Тогда между вершинами и существует еще один путь, т.е. между вершинами и существуют два реберно неперескающихся пути. Но тогда ребро не является мостом графа . Противоречие. В условиях определения (4) пусть существует такие вершины и , что между ними существует простой путь . Но тогда граф - связный. Противоречие. Возьмем и . Тогда простой путь содержит ребро . Утверждение доказано |
