Изменения

(1) '''Точка сочленения ''' [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G</tex> {{--- }} вершина, принадлежащая как минимум двум [[Отношение вершинной двусвязности#Блоки|блокам ]] <tex>G</tex>.<tex>(1)</tex>

(2) '''Точка сочленения ''' графа <tex>G</tex> {{- --}} вершина, при удалении которой в <tex>G</tex> увеличивается число [[Отношение связности, компоненты связности|компонент связности]].<tex>(2)</tex>}}[[Файл:Cut_vertex_1.png|thumb|left|335px|Вершины <tex>a_1</tex>, <tex>a_2</tex>, <tex>a_3</tex> - точки сочленения графа <tex>G</tex>.]]

Определения <tex>(1) </tex> и <tex>(2) </tex> эквивалентны. |proof=<tex>1 \Rightarrow 2</tex>  Пусть вершина <tex>v</tex> принадлежит некоторым блокам <tex>A</tex> и <tex>B</tex>. Вершине <tex>v</tex> инцидентны некоторые ребра <tex>e=uv \in A</tex> и <tex>f=wv \in B</tex>. Ребра <tex>e</tex> и <tex>f</tex> находятся в различных блоках, поэтому не существует двух непересекающихся путей между их концами. Учитывая, что один из путей между концами - путь из <tex>v</tex> в эту же вершину, получаем, что любой путь, соединяющий <tex>u</tex> и <tex>w</tex>, пройдет через <tex>v</tex>. При удалении <tex>v</tex> между <tex>u</tex> и <tex>w</tex> не останется путей, и одна из компонент связности распадется на две. <tex>2 \Rightarrow 1</tex>  Пусть <tex>v</tex> принадлежала только одному блоку <tex>C</tex>. Все вершины <tex>u_1...u_n</tex>, смежные с <tex>v</tex>, также лежат в <tex>C</tex> (в силу рефлексивности отношения вершинной двусвязности). Между каждой парой <tex>u_i, u_j</tex> вершин из <tex>u_1...u_n</tex> существует как минимум два вершинно непересекающихся пути. Теперь удалим <tex>v</tex>. Это разрушит путь <tex>u_{i}vu_{j}</tex>, но не разрушит любой оставшийся, так как иначе он тоже прошел бы через <tex>v</tex>.Рассмотрим <tex>D</tex> {{---}} компоненту связности, в которой лежала <tex>v</tex>. Пусть между вершинами <tex>u, w \in D</tex> существовал путь, проходящий через <tex>v</tex>. Но он проходил также через некоторые вершины из <tex>u_1...u_n</tex>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.}}  {{Теорема|statement=Следующие утверждения эквивалентны:# <tex>v</tex> {{---}} точка сочленения графа <tex>G</tex>;# существуют такие вершины <tex>u</tex> и <tex>w</tex>, отличные от <tex>v</tex>, что <tex>v</tex> принадлежит любому простому пути из <tex>u</tex> в <tex>w</tex>;# существует разбиение множества вершин <tex>V \setminus \{v\}</tex> на такие два подмножества <tex>U</tex> и <tex>W</tex>, что для любых вершин <tex>u \in U</tex> и <tex>w \in W</tex> вершина <tex>v</tex> принадлежит любому простому пути из <tex>u</tex> в <tex>w</tex>.

(<tex>1 ⇒ 2) Пусть вершина \Rightarrow 3</tex> Так как <tex>v</tex> принадлежит некоторым блокам {{---}} точка сочленения графа <tex>AG</tex> и , то граф <tex>BG \setminus v</tex>не связен и имеет по крайней мере две компоненты. Вершине Образуем разбиение <tex>V \setminus \{v\}</tex> инцидентны некоторые ребра , отнеся к <tex>e=uv \in AU</tex> и вершины одной из этих компонент, а к <tex>f=wv \in BW</tex>{{---}} вершины всех остальных компонент. Ребра Тогда любые две вершины <tex>eu \in U</tex> и <tex>fw \in W</tex> находятся лежат в различных блоках, поэтому не существует пары непересекающихся путей между их концами. Один из этих путей может состоять только из разных компонентах графа <tex>G \setminus v</tex>. Следовательно, поэтому любой простой путь, соединяющий из <tex>u</tex> и в <tex>w</tex>, пройдет через графа <tex>vG</tex>. При удалении содержит <tex>v</tex> между <tex>u</tex> и <tex>w</tex> не останется путей, и одна из компонент связности распадется на две.

(2 ⇒ 1) Пусть <tex>v</tex> принадлежала только одному блоку <tex>C3 \Rightarrow 2</tex>Следует из того, что (2) - частный случай (3). Все вершины  <tex>u_1...u_n2 \Rightarrow 1</tex>, смежные с Если <tex>v</tex>, также лежат принадлежит любому простому пути в <tex>CG</tex> (в силу рефлексивности отношения вершинной двусвязности). Теперь удалим <tex>v</tex>. Но <tex>u_1...u_n</tex> были концами ребер, удаленных из соединяющему <tex>Cu</tex> вместе с и <tex>vw</tex>, поэтому между каждой парой из них остался путь.Рассмотрим то в <tex>DG</tex> - компоненту связностинет простого пути, соединяющего эти вершины в которой лежала <tex>G \setminus \{v\}</tex>. Пусть между вершинами Поскольку <tex>u, w G \setminus \{v\in D}</tex> существовал путьне связен, проходящий через то <tex>v</tex>. Но он проходил также через некоторые вершины из {{---}} точка сочленения графа <tex>u_1...u_nG</tex>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.