Изменения

Два ребра <math>u_1 v_1</math> и <math>u_2 v_2</math> [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа ]] называются '''вершинно двусвязными'''(англ. ''vertex biconnected''), еслисуществуют вершинно непересекающиеся пути, соединяющие их концы.}}Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле. <math>\exist P{{Определение|definition=u_1\rightsquigarrow u_2'''Блоками''' (англ. ''block''), Q=v_1\rightsquigarrow v_2или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых — классы эквивалентности вершинной двусвязности, P\cap Q = \varnothing</math>а множества вершин {{---}} множества всевозможных концов ребер из соответствующих классов.

'''РефлексивностьСимметричность:''' Очевидно.'''Коммутативность:''' ОчевидноСледует из симметричности определения.'''Транзитивность:''' ...}} ''Замечание.'' Рассмотрим следующее определение: вершины <math>u</math> и <math>v</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> {Определение|definition=Блоками{---}} первая вершина на <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>.

==[[Точки сочленения]]=={{main|Точка сочленения, эквивалентные определения}}

'''Точка сочленения ''' (англ. ''articulation points'') графа <mathtex>G</mathtex> {{- --}} вершина, принадлежащая как минимум двум блокам <mathtex>G</mathtex>.

'''Точка сочленения ''' графа <mathtex>G</mathtex> {{- --}} вершина, при удалении которой в <mathtex>G</mathtex> увеличивается количество число компонент связности.