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

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

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

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

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

Вершины [math]a_1[/math], [math]a_2[/math], [math]a_3[/math] - точки сочленения графа [math]G[/math].

Лемма:

Определения [math](1)[/math] и [math](2)[/math] эквивалентны.

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

[math]\triangleright[/math]

[math]1 \Rightarrow 2[/math] Пусть вершина [math]v[/math] принадлежит некоторым блокам [math]A[/math] и [math]B[/math]. Вершине [math]v[/math] инцидентны некоторые ребра [math]e=uv \in A[/math] и [math]f=wv \in B[/math]. Ребра [math]e[/math] и [math]f[/math] находятся в различных блоках, поэтому не существует двух непересекающихся путей между их концами. Учитывая, что один из путей между концами - путь из [math]v[/math] в эту же вершину, получаем, что любой путь, соединяющий [math]u[/math] и [math]w[/math], пройдет через [math]v[/math]. При удалении [math]v[/math] между [math]u[/math] и [math]w[/math] не останется путей, и одна из компонент связности распадется на две. [math]2 \Rightarrow 1[/math] Пусть [math]v[/math] принадлежала только одному блоку [math]C[/math]. Все вершины [math]u_1...u_n[/math], смежные с [math]v[/math], также лежат в [math]C[/math] (в силу рефлексивности отношения вершинной двусвязности). Между каждой парой [math]u_i, u_j[/math] вершин из [math]u_1...u_n[/math] существует как минимум два вершинно непересекающихся пути. Теперь удалим [math]v[/math]. Это разрушит путь [math]u_{i}vu_{j}[/math], но не разрушит любой оставшийся, так как иначе он тоже прошел бы через [math]v[/math]. Рассмотрим [math]D[/math] — компоненту связности, в которой лежала [math]v[/math]. Пусть между вершинами [math]u, w \in D[/math] существовал путь, проходящий через [math]v[/math]. Но он проходил также через некоторые вершины из [math]u_1...u_n[/math], связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.

[math]\triangleleft[/math]

Теорема:

Следующие утверждения эквивалентны: [math]v[/math] — точка сочленения графа [math]G[/math]; существуют такие вершины [math]u[/math] и [math]w[/math], отличные от [math]v[/math], что [math]v[/math] принадлежит любому простому пути из [math]u[/math] в [math]w[/math]; существует разбиение множества вершин [math]V \setminus \{v\}[/math] на такие два подмножества [math]U[/math] и [math]W[/math], что для любых вершин [math]u \in U[/math] и [math]w \in W[/math] вершина [math]v[/math] принадлежит любому простому пути из [math]u[/math] в [math]w[/math].

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

[math]\triangleright[/math]

[math]1 \Rightarrow 3[/math] Так как [math]v[/math] — точка сочленения графа [math]G[/math], то граф [math]G \setminus v[/math] не связен и имеет по крайней мере две компоненты. Образуем разбиение [math]V \setminus \{v\}[/math], отнеся к [math]U[/math] вершины одной из этих компонент, а к [math]W[/math] — вершины всех остальных компонент. Тогда любые две вершины [math]u \in U[/math] и [math]w \in W[/math] лежат в разных компонентах графа [math]G \setminus v[/math]. Следовательно, любой простой путь из [math]u[/math] в [math]w[/math] графа [math]G[/math] содержит [math]v[/math]. [math]3 \Rightarrow 2[/math] Следует из того, что (2) - частный случай (3). [math]2 \Rightarrow 1[/math] Если [math]v[/math] принадлежит любому простому пути в [math]G[/math], соединяющему [math]u[/math] и [math]w[/math], то в [math]G[/math] нет простого пути, соединяющего эти вершины в [math]G \setminus \{v\}[/math]. Поскольку [math]G \setminus \{v\}[/math] не связен, то [math]v[/math] — точка сочленения графа [math]G[/math].

[math]\triangleleft[/math]

Источники информации

• Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009