Мост, эквивалентные определения

Материал из Викиконспекты
Версия от 22:27, 1 октября 2010; Andrey.Eremeev (обсуждение | вклад) (Новая страница: «{{Определение |definition= (1) Мост графа <math>G</math> - ребро, соединяющее как минимум две компоненты …»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
(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]