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