Изменения

Два ребра [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа ]] называются '''вершинно двусвязными''', если существует два вершинно непересекающихся пути, попарно соединяющие их концы.

Пусть ребра <mathtex>u_1u_2</mathtex>, <mathtex>v_1v_2</mathtex> и <mathtex>v_1v_2</mathtex>, <mathtex>w_1w_2</mathtex> вершинно двусвязны, и <mathtex>P_1=u_1v_1</mathtex>, <mathtex>P_2=u_2v_2</mathtex>, <mathtex>Q_1=v_1w_1</mathtex>, <mathtex>Q_2=v_2w_2</mathtex> - пути, соединяющие их концы. По определению вершинной двусвязности <mathtex>P_1 \cap Q_1 = \varnothing</mathtex> и <mathtex>P_2 \cap Q_2 = \varnothing</mathtex>. Покажем, что между <mathtex>u_1u_2</mathtex> и <mathtex>w_1w_2</mathtex> также существует 2 вершинно непересекающихся пути.

Случай 2. Пусть теперь наши пути будут пересекаться на некоторых последовательностях вершин и ребер между ними (будем называть их пересечениями). Будем называть пути, не содержащие пересечений или ребер <mathtex>u_1u_2</mathtex> или <mathtex>w_1w_2</mathtex> разрешенными. Рассмотрим следующую процедуру. Найдем пересечение <mathtex>I</mathtex>, к которому из <mathtex>v_1v_2</mathtex> есть разрешенный путь. Сожмем <mathtex>I</mathtex> и <mathtex>v_1v_2</mathtex> в две вершины, а все разрешенные пути между ними сожмем в ребро. Назначим вместо <mathtex>v_1v_2</mathtex> получившееся ребро. Будем повторять процедуру, пока остаются пересечения. Последнее получившееся ребро вершинно двусвязно с <mathtex>u_1u_2</mathtex> и <mathtex>w_1w_2</mathtex> (иначе оказалось бы, что оно не было бы вершинно двусвязно с самым первым <mathtex>v_1v_2</mathtex>). Мы свели ситуацию к Случаю 1.

''Замечание.'' Рассмотрим следующее определение: вершины <mathtex>u</mathtex> и <mathtex>v</mathtex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.

Точка сочленения графа <mathtex>G</mathtex> - вершина, принадлежащая как минимум двум блокам <mathtex>G</mathtex>.

Точка сочленения графа <mathtex>G</mathtex> - вершина, при удалении которой в <mathtex>G</mathtex> увеличивается число компонент связности.