322
правки
Изменения
первая (сырая) версия статьи
==Вершинная двусвязность==
{{Определение
|definition=
Два ребра <math>u_1 v_1</math> и <math>u_2 v_2</math> графа называются '''вершинно двусвязными''', если
<math>\exist P=u_1\rightsquigarrow u_2, Q=v_1\rightsquigarrow v_2, P\cap Q = \varnothing</math>.
}}
{{Теорема
|statement=
Отношение вершинной двусвязности является отношением эквивалентности на ребрах.
|proof=
'''Рефлексивность:''' Очевидно.
'''Коммутативность:''' Очевидно.
'''Транзитивность:''' ...
}}
''Замечание.'' Рассмотрим следующее определение: вершины <math>u</math> и <math>v</math> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
==Блоки==
{{Определение
|definition=
Блоками, или компонентами вершинной двусвязности графа, называются его подграфы, индуцированные классами эквивалентности вершинно двусвязных ребер.
}}
==Точки сочленения==
Следующие определения являются эквивалентными:
{{Определение
|definition=
Точка сочленения графа <math>G</math> - вершина, принадлежащая как минимум двум компонентам вершинной двусвязности <math>G</math>.
}}
{{Определение
|definition=
Точка сочленения графа <math>G</math> - вершина, при удалении которой в <math>G</math> увеличивается количество компонент связности.
}}
{{Определение
|definition=
Два ребра <math>u_1 v_1</math> и <math>u_2 v_2</math> графа называются '''вершинно двусвязными''', если
<math>\exist P=u_1\rightsquigarrow u_2, Q=v_1\rightsquigarrow v_2, P\cap Q = \varnothing</math>.
}}
{{Теорема
|statement=
Отношение вершинной двусвязности является отношением эквивалентности на ребрах.
|proof=
'''Рефлексивность:''' Очевидно.
'''Коммутативность:''' Очевидно.
'''Транзитивность:''' ...
}}
''Замечание.'' Рассмотрим следующее определение: вершины <math>u</math> и <math>v</math> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.
==Блоки==
{{Определение
|definition=
Блоками, или компонентами вершинной двусвязности графа, называются его подграфы, индуцированные классами эквивалентности вершинно двусвязных ребер.
}}
==Точки сочленения==
Следующие определения являются эквивалентными:
{{Определение
|definition=
Точка сочленения графа <math>G</math> - вершина, принадлежащая как минимум двум компонентам вершинной двусвязности <math>G</math>.
}}
{{Определение
|definition=
Точка сочленения графа <math>G</math> - вершина, при удалении которой в <math>G</math> увеличивается количество компонент связности.
}}
