Изменения

Перейти к: навигация, поиск

Отношение вершинной двусвязности

1935 байт убрано, 07:09, 14 октября 2010
Нет описания правки
'''Транзитивность:'''
Пусть ребра <tex>u_1u_2</tex>, <tex>v_1v_2</tex> и <tex>v_1v_2</tex>, <tex>w_1w_2</tex> вершинно двусвязны, и <tex>P_1=u_1v_1</tex>, <tex>P_2=u_2v_2</tex>, <tex>Q_1=v_1w_1</tex>, <tex>Q_2=v_2w_2</tex> - пути, соединяющие их концы. По определению вершинной двусвязности <tex>P_1 \cap Q_1 = \varnothing</tex> и <tex>P_2 \cap Q_2 = \varnothing</tex>. Покажем, что между <tex>u_1u_2</tex> и <tex>w_1w_2</tex> также существует 2 вершинно непересекающихся пути. Случай 1. Если среди всех указанных путей нет пересечений, то утверждение оказывается очевидным.Случай 2. Пусть теперь наши пути будут пересекаться на некоторых последовательностях вершин и ребер между ними (будем называть их пересечениями). Будем называть пути, не содержащие пересечений или ребер <tex>u_1u_2</tex> или <tex>w_1w_2</tex> разрешенными. Рассмотрим следующую процедуру. Найдем пересечение <tex>I</tex>, к которому из <tex>v_1v_2</tex> есть разрешенный путь. Сожмем <tex>I</tex> и <tex>v_1v_2</tex> в две вершины, а все разрешенные пути между ними сожмем в ребро. Назначим вместо <tex>v_1v_2</tex> получившееся ребро. Будем повторять процедуру, пока остаются пересечения. Последнее получившееся ребро вершинно двусвязно с <tex>u_1u_2</tex> и <tex>w_1w_2</tex> (иначе оказалось бы, что оно не было бы вершинно двусвязно с самым первым <tex>v_1v_2</tex>написано). Мы свели ситуацию к Случаю 1.
}}
Точка сочленения графа <tex>G</tex> - вершина, при удалении которой в <tex>G</tex> увеличивается число компонент связности.
}}
 
 
==Литература==
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
322
правки

Навигация