Мост, эквивалентные определения — различия между версиями
(Новая страница: «{{Определение |definition= (1) Мост графа <math>G</math> - ребро, соединяющее как минимум две компоненты …») |
|||
| Строка 17: | Строка 17: | ||
|definition= | |definition= | ||
(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> | (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> | ||
| + | }} | ||
| + | |||
| + | {{Теорема | ||
| + | |statement = Определения (1), (2), (3) и (4) эквивалентны. | ||
| + | |proof = | ||
}} | }} | ||
Версия 22:29, 1 октября 2010
| Определение: |
| (1) Мост графа - ребро, соединяющее как минимум две компоненты реберной двусвязности . |
| Определение: |
| (2) Мост графа - ребро, при удалении которого в увеличивается число компонент связности. |
| Определение: |
| (3) Ребро является мостом графа , если в существуют такие вершины и , что любой простой путь между этими вершинами проходит через ребро |
| Определение: |
| (4) Ребро является мостом графа , если существует разбиение множества вершин на такие множества и , что и ребро принадлежит любому простому пути |
| Теорема: |
Определения (1), (2), (3) и (4) эквивалентны. |
