Отношение вершинной двусвязности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вершинная двусвязность)
Строка 15: Строка 15:
 
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.
 
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.
 
<br>
 
<br>
'''Коммутативность:'''
+
'''Симметричность:'''
 
Следует из симметричности определения.
 
Следует из симметричности определения.
 
<br>
 
<br>

Версия 11:59, 23 января 2011

Эта статья находится в разработке!


Вершинная двусвязность

Определение:
Два ребра графа называются вершинно двусвязными, если они лежат на некотором вершинно простом цикле.


Теорема:
Отношение вершинной двусвязности является отношением эквивалентности на ребрах.
Доказательство:
[math]\triangleright[/math]

Рефлексивность: В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.
Симметричность: Следует из симметричности определения.
Транзитивность:

(Пока не написано. Вы можете помочь статье, написав доказательство.)
[math]\triangleleft[/math]


Замечание. Рассмотрим следующее определение: вершины [math]u[/math] и [math]v[/math] называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.

Блоки

Определение:
Блоками, или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин - множества всевозможных концов ребер из соответствующих классов.


Точки сочленения

Определение:
Точка сочленения графа [math]G[/math] - вершина, принадлежащая как минимум двум блокам [math]G[/math].


Определение:
Точка сочленения графа [math]G[/math] - вершина, при удалении которой в [math]G[/math] увеличивается число компонент связности.


См. также