Точка сочленения, эквивалентные определения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
  
 
|proof=
 
|proof=
(1 2) Пусть вершина <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>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> не останется путей, и одна из компонент связности распадется на две.
  
(2 1) Пусть <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>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>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.
 
Рассмотрим <tex>D</tex> - компоненту связности, в которой лежала <tex>v</tex>. Пусть между вершинами <tex>u, w \in D</tex> существовал путь, проходящий через <tex>v</tex>. Но он проходил также через некоторые вершины из <tex>u_1...u_n</tex>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.
 
}}
 
}}
Строка 30: Строка 30:
  
 
|proof=
 
|proof=
(1 3) Так как <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>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>.
  
(3 2) Следует из того, что (2) - частный случай (3).
+
<tex>3 \Rightarrow 2</tex> Следует из того, что (2) - частный случай (3).
  
(2 1) Если <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>.
+
<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>.
 
}}
 
}}
  

Версия 11:12, 18 января 2011

Определение:
(1) Точка сочленения графа [math]G[/math] - вершина, принадлежащая как минимум двум блокам [math]G[/math].


Определение:
(2) Точка сочленения графа [math]G[/math] - вершина, при удалении которой в [math]G[/math] увеличивается число компонент связности.


Лемма:
Определения (1) и (2) эквивалентны.
Доказательство:
[math]\triangleright[/math]

[math]1 \Rightarrow 2[/math] Пусть вершина [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] не останется путей, и одна из компонент связности распадется на две.

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


Теорема:
Следующие утверждения эквивалентны:

(1) [math]v[/math] - точка сочленения графа [math]G[/math];

(2) существуют такие вершины [math]u[/math] и [math]w[/math], отличные от [math]v[/math], что [math]v[/math] принадлежит любому простому пути из [math]u[/math] в [math]w[/math];

(3) существует разбиение множества вершин [math]V \setminus \{v\}[/math] на такие два подмножества [math]U[/math] и [math]W[/math], что для любых вершин [math]u \in U[/math] и [math]w \in W[/math] вершина [math]v[/math] принадлежит любому простому пути из [math]u[/math] в [math]w[/math].
Доказательство:
[math]\triangleright[/math]

[math]1 \Rightarrow 3[/math] Так как [math]v[/math] - точка сочленения графа [math]G[/math], то граф [math]G \setminus v[/math] не связен и имеет по крайней мере две компоненты. Образуем разбиение [math]V \setminus \{v\}[/math], отнеся к [math]U[/math] вершины одной из этих компонент, а к [math]W[/math] - вершины всех остальных компонент. Тогда любые две вершины [math]u \in U[/math] и [math]w \in W[/math] лежат в разных компонентах графа [math]G \setminus v[/math]. Следовательно, любой простой путь из [math]u[/math] в [math]w[/math] графа [math]G[/math] содержит [math]v[/math].

[math]3 \Rightarrow 2[/math] Следует из того, что (2) - частный случай (3).

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


Литература

  • Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009