Мост, эквивалентные определения — различия между версиями
| Строка 16: | Строка 16: | ||
{{Определение | {{Определение | ||
|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> принадлежит любому простому | + | (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> |
}} | }} | ||
Версия 23:05, 1 октября 2010
| Определение: |
| (1) Мост графа - ребро, соединяющее как минимум две компоненты реберной двусвязности . |
| Определение: |
| (2) Мост графа - ребро, при удалении которого в увеличивается число компонент связности. |
| Определение: |
| (3) Ребро является мостом графа , если в существуют такие вершины и , что любой простой путь между этими вершинами проходит через ребро |
| Определение: |
| (4) Ребро является мостом графа , если существует разбиение множества вершин на такие множества и , что и ребро принадлежит любому простому пути |
| Теорема: |
Определения (1), (2), (3) и (4) эквивалентны. |
