322
правки
Изменения
Нет описания правки
{{Определение
|definition=
(1) <b>'''Точка сочленения</b> ''' [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G</tex> {{--- }} вершина, принадлежащая как минимум двум блокам <tex>G</tex>.
}}
{{Определение
|definition=
(2) <b>'''Точка сочленения</b> ''' графа <tex>G</tex> {{--- }} вершина, при удалении которой в <tex>G</tex> увеличивается число [[Отношение связности, компоненты связности|компонент связности]].
}}
[[Файл:Verticl.png|thumb|left|250px|Вершины <tex>a</tex>, <tex>b</tex>, <tex>c </tex> - точки сочленения графа <tex>G</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=
Следующие утверждения эквивалентны:
(1) <tex>v</tex> {{- --}} точка сочленения графа <tex>G</tex>;
(2) существуют такие вершины <tex>u</tex> и <tex>w</tex>, отличные от <tex>v</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>.
<tex>3 \Rightarrow 2</tex> Следует из того, что (2) - частный случай (3).
<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>.
}}
