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

Вершинная двусвязность

Определение:

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

Теорема:

Отношение вершинной двусвязности является отношением эквивалентности на ребрах.

Доказательство:

[math]\triangleright[/math]

Рефлексивность: В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются. Коммутативность: Следует из симметричности определения. Транзитивность: Пусть ребра [math]u_1u_2[/math], [math]v_1v_2[/math] и [math]v_1v_2[/math], [math]w_1w_2[/math] вершинно двусвязны, и [math]P_1=u_1v_1[/math], [math]P_2=u_2v_2[/math], [math]Q_1=v_1w_1[/math], [math]Q_2=v_2w_2[/math] - пути, соединяющие их концы. По определению вершинной двусвязности [math]P_1 \cap Q_1 = \varnothing[/math] и [math]P_2 \cap Q_2 = \varnothing[/math]. Покажем, что между [math]u_1u_2[/math] и [math]w_1w_2[/math] также существует 2 вершинно непересекающихся пути. Случай 1. Если среди всех указанных путей нет пересечений, то утверждение оказывается очевидным. Случай 2. Пусть теперь наши пути будут пересекаться на некоторых последовательностях вершин и ребер между ними (будем называть их пересечениями). Будем называть пути, не содержащие пересечений или ребер [math]u_1u_2[/math] или [math]w_1w_2[/math] разрешенными. Рассмотрим следующую процедуру. Найдем пересечение [math]I[/math], к которому из [math]v_1v_2[/math] есть разрешенный путь. Сожмем [math]I[/math] и [math]v_1v_2[/math] в две вершины, а все разрешенные пути между ними сожмем в ребро. Назначим вместо [math]v_1v_2[/math] получившееся ребро. Будем повторять процедуру, пока остаются пересечения. Последнее получившееся ребро вершинно двусвязно с [math]u_1u_2[/math] и [math]w_1w_2[/math] (иначе оказалось бы, что оно не было бы вершинно двусвязно с самым первым [math]v_1v_2[/math]). Мы свели ситуацию к Случаю 1.

[math]\triangleleft[/math]

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

Блоки

Определение:

Блоками, или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин - множества концов ребер из соответствующих классов.

Точки сочленения

Определение:

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

Определение:

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