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

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

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

Два ребра [math]u_1 v_1[/math] и [math]u_2 v_2[/math] графа называются вершинно двусвязными, если [math]\exist P=u_1\rightsquigarrow u_2, Q=v_1\rightsquigarrow v_2: P\cap Q = \varnothing[/math].

Теорема:

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

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

[math]\triangleright[/math]

Рефлексивность: В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются. Коммутативность: Следует из симметричности определения. Транзитивность:

[math]\triangleleft[/math]

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

Блоки

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

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

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

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

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

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

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