322
правки
Изменения
→Вершинная двусвязность
'''Транзитивность:'''
Пусть ребра <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.
}}
