105
правок
Изменения
м
Нет описания правки
{{Определение
|definition=
Два ребра [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] называются '''вершинно двусвязными'''(англ. ''vertex biconnected''), если существует два существуют вершинно непересекающихся непересекающиеся пути, попарно соединяющие их концы.}}Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле. {{Определение|definition='''Блоками''' (англ. ''block''), или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых — классы эквивалентности вершинной двусвязности, а множества вершин {{---}} множества всевозможных концов ребер из соответствующих классов.
}}
Отношение вершинной двусвязности является отношением эквивалентности на ребрах.
|proof=
[[Файл: Vertex_biconnected.png|370px|thumb|right|К доказательству транзитивности]]
'''Рефлексивность:'''
В данном случае имеем 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>.
}}
''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
==БлокиТочки сочленения=={{Определениеmain|definition=Блоками, или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин - множества концов ребер из соответствующих классов.}} ==[[Точка сочленения, эквивалентные определения|Точки сочленения]]==}}
{{Определение
|definition=
'''Точка сочленения ''' (англ. ''articulation points'') графа <tex>G</tex> {{- --}} вершина, принадлежащая как минимум двум блокам <tex>G</tex>.
}}
{{Определение
|definition=
'''Точка сочленения ''' графа <tex>G</tex> {{- --}} вершина, при удалении которой в <tex>G</tex> увеличивается число компонент связности.
}}
== См. также ==
* [[Отношение рёберной двусвязности]]
==Источники информации==
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009
* [[wikipedia:ru:Двусвязный_граф | Википедия {{---}} Двусвязный граф]]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Связность в графах]]
