1632
правки
Изменения
м
Блоками, или компонентами вершинной двусвязности '''Точка сочленения''' (англ. ''articulation points'') графа, называют его подграфы, множества ребер которых <tex>G</tex> {{--- классы эквивалентности вершинной двусвязности}} вершина, а множества вершин - множества концов ребер из соответствующих классовпринадлежащая как минимум двум блокам <tex>G</tex>.
==[[Точка сочленения, эквивалентные определения|Точки сочленения]]==
rollbackEdits.php mass rollback
{{Определение
|definition=
Два ребра [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] называются '''вершинно двусвязными'''(англ. ''vertex biconnected''), если существует два существуют вершинно непересекающихся непересекающиеся пути, попарно соединяющие их концы.}}Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле. {{Определение|definition='''Блоками''' (англ. ''block''), или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых — классы эквивалентности вершинной двусвязности, а множества вершин {{---}} множества всевозможных концов ребер из соответствующих классов.
}}
Отношение вершинной двусвязности является отношением эквивалентности на ребрах.
|proof=
[[Файл: Vertex_biconnected.png|370px|thumb|right|К доказательству транзитивности]]
'''Рефлексивность:'''
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.
'''КоммутативностьСимметричность:'''
Следует из симметричности определения.
'''Транзитивность:'''
Пусть имеем ребра : <tex>u_1u_2ef</tex> вершинно двусвязно с <tex>cd</tex>, <tex>v_1v_2cd</tex> и вершинно двусвязно с <tex>v_1v_2ab</tex>, при этом все они различны. Ребра <tex>w_1w_2ef</tex> вершинно двусвязны, и <tex>P_1=u_1v_1cd</tex>, лежат на вершинно простом цикле <tex>P_2=u_2v_2C</tex>. Будем считать, что существуют непересекающиеся пути <tex>Q_1=v_1w_1P : a \leadsto c</tex>, <tex>Q_2=v_2w_2Q : b \leadsto d</tex> - пути(ситуация, когда они идут наоборот, соединяющие их концыразбирается аналогично). По определению вершинной двусвязности Пусть <tex>P_1 \cap Q_1 = \varnothingx</tex> и {{---}} первая вершина на <tex>P_2 \cap Q_2 = \varnothingP</tex>. Покажем, что между лежащая также на <tex>u_1u_2C</tex> и , <tex>w_1w_2y</tex> также существует 2 вершинно непересекающихся пути. Случай 1. Если среди всех указанных путей нет пересечений, то утверждение оказывается очевидным.Случай 2. Пусть теперь наши пути будут пересекаться {{---}} первая вершина на некоторых последовательностях вершин и ребер между ними (будем называть их пересечениями). Будем называть пути, не содержащие пересечений или ребер <tex>u_1u_2Q</tex> или , лежащая на <tex>w_1w_2C</tex> разрешенными. Рассмотрим следующую процедуру. Найдем пересечение Проделав пути от <tex>Ia</tex>, к которому из до <tex>v_1v_2x</tex> есть разрешенный путь. Сожмем и от <tex>Ib</tex> и до <tex>v_1v_2y</tex> в две вершины, а все разрешенные пути между ними сожмем в ребро. Назначим вместо далее пойдем по циклу <tex>v_1v_2C</tex> получившееся ребро. Будем повторять процедурув нужные (различные) стороны, пока остаются пересечения. Последнее получившееся ребро вершинно двусвязно с чтобы достичь <tex>u_1u_2e</tex> и <tex>w_1w_2f</tex>. То есть <tex>ef</tex> (иначе оказалось бы, что оно не было бы вершинно двусвязно с самым первым <tex>v_1v_2ab</tex>). Мы свели ситуацию к Случаю 1.
}}
''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
==БлокиТочки сочленения=={{main|Точка сочленения, эквивалентные определения}}
{{Определение
|definition=
}}
{{Определение
|definition=
'''Точка сочленения ''' графа <tex>G</tex> {{--- вершина, принадлежащая как минимум двум блокам <tex>G</tex>.}}{{Определение|definition=Точка сочленения графа <tex>G</tex> - вершина, при удалении которой в <tex>G</tex> увеличивается число компонент связности.
}}
== См. также ==
* [[Отношение рёберной двусвязности]]
==Источники информации==
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
* [[wikipedia:ru:Двусвязный_граф | Википедия {{---}} Двусвязный граф]]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Связность в графах]]
