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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вершинная двусвязность)
(Вершинная двусвязность)
Строка 20: Строка 20:
  
 
Случай 1. Если среди всех указанных путей нет пересечений, то утверждение оказывается очевидным.
 
Случай 1. Если среди всех указанных путей нет пересечений, то утверждение оказывается очевидным.
Случай 2. Пусть теперь наши пути будут пересекаться на некоторых последовательностях вершин и ребер между ними (будем называть их пересечениями). Будем называть пути, не содержащие пересечений или ребер <math>u_1u_2</math> или <math>w_1w_2</math> разрешенными. Рассмотрим следующую процедуру. Найдем пересечение <math>I</math>, к которому из <math>v_1v_2</math> есть разрешенный путь. Сожмем <math>I</math> и <math>v_1v_2</math> в две вершины, а все разрешенные пути между ними сожмем в ребро. Назначим вместо <math>v_1v_2</math> получившееся ребро. Будем повторять процедуру, пока остаются пересечения. Последнее получившееся ребро вершинно двусвязно с <math>u_1u_2</math> и <math>w_1w_2</math> (иначе оказалось бы, что оно не было бы вершинно двусвязно с самым первым <math>v_1v_2<.math>). Мы свели ситуацию к Случаю 1.
+
Случай 2. Пусть теперь наши пути будут пересекаться на некоторых последовательностях вершин и ребер между ними (будем называть их пересечениями). Будем называть пути, не содержащие пересечений или ребер <math>u_1u_2</math> или <math>w_1w_2</math> разрешенными. Рассмотрим следующую процедуру. Найдем пересечение <math>I</math>, к которому из <math>v_1v_2</math> есть разрешенный путь. Сожмем <math>I</math> и <math>v_1v_2</math> в две вершины, а все разрешенные пути между ними сожмем в ребро. Назначим вместо <math>v_1v_2</math> получившееся ребро. Будем повторять процедуру, пока остаются пересечения. Последнее получившееся ребро вершинно двусвязно с <math>u_1u_2</math> и <math>w_1w_2</math> (иначе оказалось бы, что оно не было бы вершинно двусвязно с самым первым <math>v_1v_2</math>). Мы свели ситуацию к Случаю 1.
 
}}
 
}}
  

Версия 12:20, 11 октября 2010

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

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


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

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

Коммутативность: Следует из симметричности определения.

Транзитивность: Пусть ребра [math]u_1u_2[/math], [math]v_1v_2[/math] и [math]v_1v_2[/math], [math]w_1w_2[/math] вершинно двусвязны, и [math]P_1=u_1v_1[/math], [math]P_2=u_2v_2[/math], [math]Q_1=v_1w_1[/math], [math]Q_2=v_2w_2[/math] - пути, соединяющие их концы. По определению вершинной двусвязности [math]P_1 \cap Q_1 = \varnothing[/math] и [math]P_2 \cap Q_2 = \varnothing[/math]. Покажем, что между [math]u_1u_2[/math] и [math]w_1w_2[/math] также существует 2 вершинно непересекающихся пути.

Случай 1. Если среди всех указанных путей нет пересечений, то утверждение оказывается очевидным.

Случай 2. Пусть теперь наши пути будут пересекаться на некоторых последовательностях вершин и ребер между ними (будем называть их пересечениями). Будем называть пути, не содержащие пересечений или ребер [math]u_1u_2[/math] или [math]w_1w_2[/math] разрешенными. Рассмотрим следующую процедуру. Найдем пересечение [math]I[/math], к которому из [math]v_1v_2[/math] есть разрешенный путь. Сожмем [math]I[/math] и [math]v_1v_2[/math] в две вершины, а все разрешенные пути между ними сожмем в ребро. Назначим вместо [math]v_1v_2[/math] получившееся ребро. Будем повторять процедуру, пока остаются пересечения. Последнее получившееся ребро вершинно двусвязно с [math]u_1u_2[/math] и [math]w_1w_2[/math] (иначе оказалось бы, что оно не было бы вершинно двусвязно с самым первым [math]v_1v_2[/math]). Мы свели ситуацию к Случаю 1.
[math]\triangleleft[/math]

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

Блоки

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


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

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


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