Отношение вершинной двусвязности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Вершинная двусвязность)
м (rollbackEdits.php mass rollback)
 
(не показаны 53 промежуточные версии 10 участников)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Два ребра графа называются '''вершинно двусвязными''', если существует два вершинно непересекающихся пути, попарно соединяющие их концы.
+
Два ребра [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] называются '''вершинно двусвязными''' (англ. ''vertex biconnected''), если существуют вершинно непересекающиеся пути, соединяющие их концы.
 +
}}
 +
Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле.
 +
 
 +
{{Определение
 +
|definition=
 +
'''Блоками''' (англ. ''block''), или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых — классы эквивалентности вершинной двусвязности, а множества вершин {{---}} множества всевозможных концов ребер из соответствующих классов.
 
}}
 
}}
  
Строка 9: Строка 15:
 
Отношение вершинной двусвязности является отношением эквивалентности на ребрах.
 
Отношение вершинной двусвязности является отношением эквивалентности на ребрах.
 
|proof=
 
|proof=
−
 
+
[[Файл: Vertex_biconnected.png|370px|thumb|right|К доказательству транзитивности]]
 
'''Рефлексивность:'''
 
'''Рефлексивность:'''
 
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.
 
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.
  
−
'''Коммутативность:'''
+
'''Симметричность:'''
 
Следует из симметричности определения.
 
Следует из симметричности определения.
  
 
'''Транзитивность:'''
 
'''Транзитивность:'''
−
Пусть ребра <math>u_1u_2</math>, <math>v_1v_2</math> и <math>v_1v_2</math>, <math>w_1w_2</math> вершинно двусвязны, и <math>P_1=u_1v_1</math>, <math>P_2=u_2v_2</math>, <math>Q_1=v_1w_1</math>, <math>Q_2=v_2w_2</math> - пути, соединяющие их концы. По определению вершинной двусвязности <math>P_1 \cap Q_1 = \varnothing</math> и <math>P_2 \cap Q_2 = \varnothing</math>. Покажем, что между <math>u_1u_2</math> и <math>w_1w_2</math> также существует 2 вершинно непересекающихся пути.
+
Пусть имеем ребра: <tex>ef</tex> вершинно двусвязно с <tex>cd</tex>, <tex>cd</tex> вершинно двусвязно с <tex>ab</tex>, при этом все они различны. Ребра <tex>ef</tex> и <tex>cd</tex> лежат на вершинно простом цикле <tex>C</tex>. Будем считать, что существуют непересекающиеся пути <tex>P : a \leadsto c</tex>, <tex>Q : b \leadsto d</tex> (ситуация, когда они идут наоборот, разбирается аналогично). Пусть <tex>x</tex> {{---}} первая вершина на <tex>P</tex>, лежащая также на <tex>C</tex>, <tex>y</tex> {{---}} первая вершина на <tex>Q</tex>, лежащая на <tex>C</tex>. Проделав пути от <tex>a</tex> до <tex>x</tex> и от <tex>b</tex> до <tex>y</tex>, далее пойдем по циклу <tex>C</tex> в нужные (различные) стороны, чтобы достичь <tex>e</tex> и <tex>f</tex>. То есть <tex>ef</tex> вершинно двусвязно с <tex>ab</tex>.
−
 
 
−
Случай 1. Если среди всех указанных путей нет пересечений, то утверждение оказывается очевидным.
 
−
Случай 2. Пусть теперь наши пути будут пересекаться на некоторых последовательностях вершин и ребер между ними (будем называть их пересечениями). Будем называть пути, не содержащие пересечений или ребер <math>u_1u_2</math> или <math>w_1w_2</math> разрешенными. Рассмотрим следующую процедуру. Найдем пересечение <math>I</math>, к которому из <math>v_1v_2</math> есть разрешенный путь. Сожмем <math>I</math> и <math>v_1v_2</math> в две вершины, а все разрешенные пути между ними сожмем в ребро. Назначим вместо <math>v_1v_2</math> получившееся ребро. Будем повторять процедуру, пока остаются пересечения. Последнее получившееся ребро вершинно двусвязно с <math>u_1u_2</math> и <math>w_1w_2</math> (иначе оказалось бы, что оно не было бы вершинно двусвязно с самым первым <math>v_1v_2<.math>). Мы свели ситуацию к Случаю 1.
 
 
}}
 
}}
  
−
''Замечание.'' Рассмотрим следующее определение: вершины <math>u</math> и <math>v</math> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
+
''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
  
−
==Блоки==
+
==Точки сочленения==
 +
{{main|Точка сочленения, эквивалентные определения}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Блоками, или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин - множества концов ребер из соответствующих классов.
+
'''Точка сочленения''' (англ. ''articulation points'') графа <tex>G</tex> {{---}} вершина, принадлежащая как минимум двум блокам <tex>G</tex>.
 
}}
 
}}
−
 
−
==[[Точка сочленения, эквивалентные определения|Точки сочленения]]==
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Точка сочленения графа <math>G</math> - вершина, принадлежащая как минимум двум блокам <math>G</math>.
+
'''Точка сочленения''' графа <tex>G</tex> {{---}} вершина, при удалении которой в <tex>G</tex> увеличивается число компонент связности.
−
}}
 
−
{{Определение
 
−
|definition=
 
−
Точка сочленения графа <math>G</math> - вершина, при удалении которой в <math>G</math> увеличивается число компонент связности.
 
 
}}
 
}}
 +
 +
== См. также ==
 +
* [[Отношение рёберной двусвязности]]
 +
 +
==Источники информации==
 +
*  Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
 +
* [[wikipedia:ru:Двусвязный_граф | Википедия {{---}} Двусвязный граф]]
 +
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Связность в графах]]

Текущая версия на 19:33, 4 сентября 2022

Вершинная двусвязность

Определение:
Два ребра графа называются вершинно двусвязными (англ. vertex biconnected), если существуют вершинно непересекающиеся пути, соединяющие их концы.

Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле.


Определение:
Блоками (англ. block), или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых — классы эквивалентности вершинной двусвязности, а множества вершин — множества всевозможных концов ребер из соответствующих классов.


Теорема:
Отношение вершинной двусвязности является отношением эквивалентности на ребрах.
Доказательство:
[math]\triangleright[/math]
К доказательству транзитивности

Рефлексивность: В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.

Симметричность: Следует из симметричности определения.

Транзитивность:

Пусть имеем ребра: [math]ef[/math] вершинно двусвязно с [math]cd[/math], [math]cd[/math] вершинно двусвязно с [math]ab[/math], при этом все они различны. Ребра [math]ef[/math] и [math]cd[/math] лежат на вершинно простом цикле [math]C[/math]. Будем считать, что существуют непересекающиеся пути [math]P : a \leadsto c[/math], [math]Q : b \leadsto d[/math] (ситуация, когда они идут наоборот, разбирается аналогично). Пусть [math]x[/math] — первая вершина на [math]P[/math], лежащая также на [math]C[/math], [math]y[/math] — первая вершина на [math]Q[/math], лежащая на [math]C[/math]. Проделав пути от [math]a[/math] до [math]x[/math] и от [math]b[/math] до [math]y[/math], далее пойдем по циклу [math]C[/math] в нужные (различные) стороны, чтобы достичь [math]e[/math] и [math]f[/math]. То есть [math]ef[/math] вершинно двусвязно с [math]ab[/math].
[math]\triangleleft[/math]

Замечание. Рассмотрим следующее определение: вершины [math]u[/math] и [math]v[/math] называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.

Точки сочленения

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


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


См. также

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Отношение_вершинной_двусвязности&oldid=85463»