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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Добавлена теорема)
(не показано 17 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
(1) <b>Точка сочленения</b> [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G</tex> - вершина, принадлежащая как минимум двум блокам <tex>G</tex>.
+
'''Точка сочленения''' [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G</tex> {{---}} вершина, принадлежащая как минимум двум [[Отношение вершинной двусвязности#Блоки|блокам]] <tex>G</tex>. <tex>(1)</tex>
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
(2) <b>Точка сочленения</b> графа <tex>G</tex> - вершина, при удалении которой в <tex>G</tex> увеличивается число [[Отношение связности, компоненты связности|компонент связности]].
+
'''Точка сочленения''' графа <tex>G</tex> {{---}} вершина, при удалении которой в <tex>G</tex> увеличивается число [[Отношение связности, компоненты связности|компонент связности]]. <tex>(2)</tex>
 
}}
 
}}
[[Файл:Verticles.png]]
+
[[Файл:Cut_vertex_1.png|thumb|left|335px|Вершины <tex>a_1</tex>, <tex>a_2</tex>, <tex>a_3</tex> - точки сочленения графа <tex>G</tex>.]]
 +
 
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Определения (1) и (2) эквивалентны.
+
Определения <tex>(1)</tex> и <tex>(2)</tex> эквивалентны.
  
 
|proof=
 
|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>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>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>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>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.
+
Рассмотрим <tex>D</tex> {{---}} компоненту связности, в которой лежала <tex>v</tex>. Пусть между вершинами <tex>u, w \in D</tex> существовал путь, проходящий через <tex>v</tex>. Но он проходил также через некоторые вершины из <tex>u_1...u_n</tex>, связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.
 
}}
 
}}
  
Строка 23: Строка 28:
 
|statement=
 
|statement=
 
Следующие утверждения эквивалентны:
 
Следующие утверждения эквивалентны:
(1) <tex>v</tex> - точка сочленения графа <tex>G</tex>;
+
# <tex>v</tex> {{---}} точка сочленения графа <tex>G</tex>;
 +
# существуют такие вершины <tex>u</tex> и <tex>w</tex>, отличные от <tex>v</tex>, что <tex>v</tex> принадлежит любому простому пути из <tex>u</tex> в <tex>w</tex>;
 +
# существует разбиение множества вершин <tex>V \setminus \{v\}</tex> на такие два подмножества <tex>U</tex> и <tex>W</tex>, что для любых вершин <tex>u \in U</tex> и <tex>w \in W</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>.
 +
}}
  
(2) существуют такие вершины <tex>u</tex> и <tex>w</tex>, отличные от <tex>v</tex>, что <tex>v</tex> принадлежит любому простому пути из <tex>u</tex> в <tex>w</tex>;
 
  
(3) существует разбиение множества вершин <tex>V \setminus \{v\}</tex> на такие два подмножества <tex>U</tex> и <tex>W</tex>, что для любых вершин <tex>u \in U</tex> и <tex>w \in W</tex> вершина <tex>v</tex> принадлежит любому простому пути из <tex>u</tex> в <tex>w</tex>.
+
{{Теорема
 +
|statement=
 +
Пусть <tex>G</tex> {{---}} связный граф с не менее чем тремя вершинами. Следующие утверждения эквивалентны:
 +
# <tex>G</tex> {{---}} блок ;
 +
# любые две вершины графа <tex>G</tex> принадлежат некоторому общему простому циклу;
 +
# любая вершина и любое ребро графа <tex>G</tex> принадлежат некоторому общему простому циклу;
 +
# любые два ребра графа <tex>G</tex> принадлежат некоторому общему простому циклу;
 +
# для любых двух вершин и любого ребра графа <tex>G</tex> существует простая цепь, соединяющая эти вершины и включающая данное ребро;
 +
# для любых трех различных вершин графа <tex>G</tex> существует простая цепь, соединяющая две из них и проходящая через третью;
 +
# для каждых трех различных вершин графа <tex>G</tex> существует простая цепь, соединяющая  две из них и не проходящая через третью.
  
 
|proof=
 
|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>1 \Rightarrow 2</tex> Пусть <tex>u</tex>,<tex>v</tex> - различные вершины графа <tex>G</tex>, а <tex>U</tex> - множество вершин, отличных от <tex>u</tex>, которые лежат на простом цикле, содержащем <tex>u</tex>. Поскольку в <tex>G</tex> по крайней мере три вершины и нет точек сочленения, то в <tex>G</tex> нет также мостов. Значит, каждая вершина, смежная с <tex>u</tex>, принадлежит <tex>U</tex>, т.е. <tex>U</tex> не пусто. Предположим, что <tex>u</tex> не принадлежит <tex>U</tex>. Пусть <tex>w</tex> - вершина в <tex>U</tex>, для которой расстояние <tex>d</tex>(<tex>w</tex>-<tex>u</tex>)-цепь минимально. Пусть <tex>P_0</tex> - кратчайшая простая (<tex>w</tex>-<tex>u</tex>)- цепь, а <tex>P_1</tex> и <tex>P_2</tex> -  две простые (<tex>u</tex>-<tex>w</tex>)-цепи цикла, содержащего <tex>u</tex> и <tex>w</tex>. Так как <tex>w</tex> не является точкой сочленения, то существует простая (<tex>u</tex>-<tex>v</tex>)-цепь <tex>P'</tex>, не содержащая <tex>w</tex>. Обозначим через <tex>w'</tex> ближайшую к <tex>u</tex> вершину, принадлежащую <tex>P'</tex>, которая также принадлежит <tex>P_0</tex>, и через <tex>u'</tex> последнюю вершину (<tex>u</tex>-<tex>w'</tex>)-подцепи в <tex>P'</tex>, которая принадлежит или <tex>P_1</tex>, или <tex>P_2</tex>. Не теряя общности, предположим, что <tex>u</tex>' принадлежит  <tex>P_1</tex>.
 +
Пусть <tex>Q_1</tex> - простая (<tex>u</tex>-<tex>w'</tex>)-цепь, содержащая (<tex>u</tex>-<tex>u'</tex>)-подцепь цепи <tex>P_1</tex> и (<tex>u'</tex>-<tex>w'</tex>)-подцепь цепи  <tex>P'</tex>, а <tex>Q_2</tex> - простая (<tex>u</tex>-<tex>w'</tex>)-подцепь, содержащая <tex>P_2</tex> вслед за (<tex>w</tex>-<tex>w</tex>')-подцепью цепи <tex>P_0</tex>. Ясно, что <tex>Q_1</tex> и <tex>Q_2</tex> - непересекающиеся простые (<tex>u</tex>-<tex>w'</tex>)-цепи. Вместе они образуют простой цикл, так что <tex>w'</tex> принадлежит <tex>U</tex>. Поскольку <tex>w'</tex> принадлежит кратчайшей цепи, <tex>d</tex>(<tex>w'</tex>,<tex>u</tex>)<<tex>d</tex>(<tex>w</tex>,<tex>u</tex>). Это противоречит выбору <tex>w</tex> и, следовательно,  доказывает, что <tex>u</tex> и <tex>v</tex> лежат на одном простом цикле.
  
 
<tex>3 \Rightarrow 2</tex> Следует из того, что (2) - частный случай (3).
 
<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>.
+
<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>.
 
}}
 
}}
  
  
==Литература==
+
==Источники информации==
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
+
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
 +
 
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Связность в графах]]

Версия 16:53, 8 мая 2016

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


Определение:
Точка сочленения графа [math]G[/math] — вершина, при удалении которой в [math]G[/math] увеличивается число компонент связности. [math](2)[/math]
Вершины [math]a_1[/math], [math]a_2[/math], [math]a_3[/math] - точки сочленения графа [math]G[/math].
Лемма:
Определения [math](1)[/math] и [math](2)[/math] эквивалентны.
Доказательство:
[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]u_i, u_j[/math] вершин из [math]u_1...u_n[/math] существует как минимум два вершинно непересекающихся пути. Теперь удалим [math]v[/math]. Это разрушит путь [math]u_{i}vu_{j}[/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]


Теорема:
Пусть [math]G[/math] — связный граф с не менее чем тремя вершинами. Следующие утверждения эквивалентны:
  1. [math]G[/math] — блок ;
  2. любые две вершины графа [math]G[/math] принадлежат некоторому общему простому циклу;
  3. любая вершина и любое ребро графа [math]G[/math] принадлежат некоторому общему простому циклу;
  4. любые два ребра графа [math]G[/math] принадлежат некоторому общему простому циклу;
  5. для любых двух вершин и любого ребра графа [math]G[/math] существует простая цепь, соединяющая эти вершины и включающая данное ребро;
  6. для любых трех различных вершин графа [math]G[/math] существует простая цепь, соединяющая две из них и проходящая через третью;
  7. для каждых трех различных вершин графа [math]G[/math] существует простая цепь, соединяющая две из них и не проходящая через третью.
Доказательство:
[math]\triangleright[/math]

[math]1 \Rightarrow 2[/math] Пусть [math]u[/math],[math]v[/math] - различные вершины графа [math]G[/math], а [math]U[/math] - множество вершин, отличных от [math]u[/math], которые лежат на простом цикле, содержащем [math]u[/math]. Поскольку в [math]G[/math] по крайней мере три вершины и нет точек сочленения, то в [math]G[/math] нет также мостов. Значит, каждая вершина, смежная с [math]u[/math], принадлежит [math]U[/math], т.е. [math]U[/math] не пусто. Предположим, что [math]u[/math] не принадлежит [math]U[/math]. Пусть [math]w[/math] - вершина в [math]U[/math], для которой расстояние [math]d[/math]([math]w[/math]-[math]u[/math])-цепь минимально. Пусть [math]P_0[/math] - кратчайшая простая ([math]w[/math]-[math]u[/math])- цепь, а [math]P_1[/math] и [math]P_2[/math] - две простые ([math]u[/math]-[math]w[/math])-цепи цикла, содержащего [math]u[/math] и [math]w[/math]. Так как [math]w[/math] не является точкой сочленения, то существует простая ([math]u[/math]-[math]v[/math])-цепь [math]P'[/math], не содержащая [math]w[/math]. Обозначим через [math]w'[/math] ближайшую к [math]u[/math] вершину, принадлежащую [math]P'[/math], которая также принадлежит [math]P_0[/math], и через [math]u'[/math] последнюю вершину ([math]u[/math]-[math]w'[/math])-подцепи в [math]P'[/math], которая принадлежит или [math]P_1[/math], или [math]P_2[/math]. Не теряя общности, предположим, что [math]u[/math]' принадлежит  [math]P_1[/math]. Пусть [math]Q_1[/math] - простая ([math]u[/math]-[math]w'[/math])-цепь, содержащая ([math]u[/math]-[math]u'[/math])-подцепь цепи [math]P_1[/math] и ([math]u'[/math]-[math]w'[/math])-подцепь цепи [math]P'[/math], а [math]Q_2[/math] - простая ([math]u[/math]-[math]w'[/math])-подцепь, содержащая [math]P_2[/math] вслед за ([math]w[/math]-[math]w[/math]')-подцепью цепи [math]P_0[/math]. Ясно, что [math]Q_1[/math] и [math]Q_2[/math] - непересекающиеся простые ([math]u[/math]-[math]w'[/math])-цепи. Вместе они образуют простой цикл, так что [math]w'[/math] принадлежит [math]U[/math]. Поскольку [math]w'[/math] принадлежит кратчайшей цепи, [math]d[/math]([math]w'[/math],[math]u[/math])<[math]d[/math]([math]w[/math],[math]u[/math]). Это противоречит выбору [math]w[/math] и, следовательно, доказывает, что [math]u[/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