Изменения

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

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

52 байта добавлено, 07:07, 24 сентября 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>, поэтому между каждой парой из них остался путь.
322
правки

Навигация