322
правки
Изменения
первая (сырая) версия статьи
Следующие определения являются эквивалентными:
{{Определение
|definition=
(1) Точка сочленения графа <math>G</math> - вершина, принадлежащая как минимум двум блокам <math>G</math>.
}}
{{Определение
|definition=
(2) Точка сочленения графа <math>G</math> - вершина, при удалении которой в <math>G</math> увеличивается количество компонент связности.}}
{{Утверждение
|statement=
Определения (1) и (2) эквивалентны.
|proof=
(1 ⇒ 2) Пусть вершина <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> не останется путей, и одна из компонент связности распадется на две.
(2 ⇒ 1) Пусть <math>v</math> принадлежала только одному блоку <math>C</math>. Все вершины <math>u_1...u_n</math>, смежные с <math>v</math>, также лежат в <math>C</math> (в силу рефлексивности отношения вершинной двусвязности). Теперь удалим <math>v</math>. Но <math>u_1...u_n</math> были концами ребер, удаленных из <math>C</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>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.
}}
{{Определение
|definition=
(1) Точка сочленения графа <math>G</math> - вершина, принадлежащая как минимум двум блокам <math>G</math>.
}}
{{Определение
|definition=
(2) Точка сочленения графа <math>G</math> - вершина, при удалении которой в <math>G</math> увеличивается количество компонент связности.}}
{{Утверждение
|statement=
Определения (1) и (2) эквивалентны.
|proof=
(1 ⇒ 2) Пусть вершина <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> не останется путей, и одна из компонент связности распадется на две.
(2 ⇒ 1) Пусть <math>v</math> принадлежала только одному блоку <math>C</math>. Все вершины <math>u_1...u_n</math>, смежные с <math>v</math>, также лежат в <math>C</math> (в силу рефлексивности отношения вершинной двусвязности). Теперь удалим <math>v</math>. Но <math>u_1...u_n</math> были концами ребер, удаленных из <math>C</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>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.
}}
