Изменения

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

(2) <b>'''Точка сочленения</b> ''' графа <tex>G</tex> {{--- }} вершина, при удалении которой в <tex>G</tex> увеличивается число [[Отношение связности, компоненты связности|компонент связности]].<tex>(2)</tex>

[[Файл:VerticlCut_vertex_1.png|thumb|left|250px335px|Вершины a<tex>a_1</tex>, b<tex>a_2</tex>, c <tex>a_3</tex> - точки сочленения графа <tex>G</tex>.]]

Определения <tex>(1) </tex> и <tex>(2) </tex> эквивалентны.

<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>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>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.

(# <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>. |proof=<tex>1) \Rightarrow 3</tex> Так как <tex>v</tex> {{--- }} точка сочленения графа <tex>G</tex>;, то граф <tex>G \setminus v</tex> не связен и имеет по крайней мере две компоненты. Образуем разбиение <tex>V \setminus \{v\}</tex>, отнеся к <tex>U</tex> вершины одной из этих компонент, а к <tex>W</tex> {{---}} вершины всех остальных компонент. Тогда любые две вершины <tex>u \in U</tex> и <tex>w \in W</tex> лежат в разных компонентах графа <tex>G \setminus v</tex>. Следовательно, любой простой путь из <tex>u</tex> в <tex>w</tex> графа <tex>G</tex> содержит <tex>v</tex>.

(2) существуют такие вершины <tex>u</tex> и <tex>w</tex>, отличные от <tex>v3 \Rightarrow 2</tex>Следует из того, что <tex>v</tex> принадлежит любому простому пути из <tex>u</tex> в <tex>w</tex>;(2) - частный случай (3).

(3) существует разбиение множества вершин <tex>V 2 \Rightarrow 1</tex> Если <tex>v</tex> принадлежит любому простому пути в <tex>G</tex>, соединяющему <tex>u</tex> и <tex>w</tex>, то в <tex>G</tex> нет простого пути, соединяющего эти вершины в <tex>G \setminus \{v\}</tex>. Поскольку <tex>G \setminus \{v\}</tex> на такие два подмножества не связен, то <tex>v</tex> {{---}} точка сочленения графа <tex>G</tex>.}}  {{Теорема|statement=Пусть <tex>UG</tex> и {{---}} связный граф с не менее чем тремя вершинами. Следующие утверждения эквивалентны:# <tex>WG</tex>, что для любых вершин {{---}} блок ;# любые две вершины графа <tex>u \in UG</tex> принадлежат некоторому общему простому циклу;# любая вершина и любое ребро графа <tex>w \in WG</tex> вершина принадлежат некоторому общему простому циклу;# любые два ребра графа <tex>vG</tex> принадлежит любому принадлежат некоторому общему простому пути из циклу;# для любых двух вершин и любого ребра графа <tex>G</tex> существует простая цепь, соединяющая эти вершины и включающая данное ребро;# для любых трех различных вершин графа <tex>uG</tex> в существует простая цепь, соединяющая две из них и проходящая через третью;# для каждых трех различных вершин графа <tex>wG</tex>существует простая цепь, соединяющая две из них и не проходящая через третью.

<tex>1 \Rightarrow 32</tex> Так как Пусть <tex>u</tex>,<tex>v</tex> - точка сочленения различные вершины графа <tex>G</tex>, а <tex>U</tex> - множество вершин, отличных от <tex>u</tex>, которые лежат на простом цикле, содержащем <tex>u</tex>. Поскольку в <tex>G</tex> по крайней мере три вершины и нет точек сочленения, то граф в <tex>G \setminus v</tex> нет также мостов. Значит, каждая вершина, смежная с <tex>u</tex>, принадлежит <tex>U</tex>, т.е. <tex>U</tex> не пусто. Предположим, что <tex>u</tex> не связен принадлежит <tex>U</tex>. Пусть <tex>w</tex> - вершина в <tex>U</tex>, для которой расстояние <tex>d</tex>(<tex>w</tex>-<tex>u</tex>)-цепь минимально. Пусть <tex>P_0</tex> - кратчайшая простая (<tex>w</tex>-<tex>u</tex>)- цепь, а <tex>P_1</tex> и имеет по крайней мере <tex>P_2</tex> - две компонентыпростые (<tex>u</tex>-<tex>w</tex>)-цепи цикла, содержащего <tex>u</tex> и <tex>w</tex>. Образуем разбиение Так как <tex>w</tex> не является точкой сочленения, то существует простая (<tex>u</tex>-<tex>V \setminus \{v\}</tex>)-цепь <tex>P'</tex>, отнеся не содержащая <tex>w</tex>. Обозначим через <tex>w'</tex> ближайшую к <tex>Uu</tex> вершину, принадлежащую <tex>P'</tex>, которая также принадлежит <tex>P_0</tex> вершины одной из этих компонент, а к и через <tex>u'</tex> последнюю вершину (<tex>u</tex>-<tex>Ww'</tex> )- вершины всех остальных компонентподцепи в <tex>P'</tex>, которая принадлежит или <tex>P_1</tex>, или <tex>P_2</tex>. Не теряя общности, предположим, что <tex>u</tex>' принадлежит  <tex>P_1</tex>. Тогда любые две вершины Пусть <tex>Q_1</tex> - простая (<tex>u</tex>-<tex>w'</tex>)-цепь, содержащая (<tex>u</tex>-<tex>u \in U'</tex>)-подцепь цепи <tex>P_1</tex> и (<tex>u'</tex>-<tex>w'</tex>)-подцепь цепи <tex>P'</tex>, а <tex>Q_2</tex> - простая (<tex>u</tex>-<tex>w'</tex>)-подцепь, содержащая <tex>P_2</tex> вслед за (<tex>w \in W</tex> лежат в разных компонентах графа -<tex>w</tex>')-подцепью цепи <tex>G \setminus vP_0</tex>. СледовательноЯсно, любой что <tex>Q_1</tex> и <tex>Q_2</tex> - непересекающиеся простые (<tex>u</tex>-<tex>w'</tex>)-цепи. Вместе они образуют простой путь из цикл, так что <tex>w'</tex> принадлежит <tex>U</tex>. Поскольку <tex>w'</tex> принадлежит кратчайшей цепи, <tex>d</tex>(<tex>w'</tex>,<tex>u</tex>)<<tex>d</tex>(<tex>w</tex>,<tex>u</tex> в ). Это противоречит выбору <tex>w</tex> графа и, следовательно, доказывает, что <tex>Gu</tex> содержит и <tex>v</tex>лежат на одном простом цикле.

<tex>2 \Rightarrow 1</tex> Если <tex>v</tex> принадлежит любому простому пути в <tex>G</tex>, соединяющему <tex>u</tex> и <tex>w</tex>, то в <tex>G</tex> нет простого пути, соединяющего эти вершины в <tex>G \setminus \{v\}</tex>. Поскольку <tex>G \setminus \{v\}</tex> не связен, то <tex>v</tex> {{- --}} точка сочленения графа <tex>G</tex>.

==ЛитератураИсточники информации==* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009 [[Категория:Алгоритмы и структуры данных]][[Категория:Связность в графах]]