Мост, эквивалентные определения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |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) Мост графа [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) эквивалентны.