Изменения

Перейти к: навигация, поиск

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

94 байта добавлено, 11:12, 18 января 2011
Нет описания правки
|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>v</tex>. Но <tex>u_1...u_n</tex> были концами ребер, удаленных из <tex>C</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>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.
}}
|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>.
}}
Анонимный участник

Навигация