228
правок
Изменения
→Реберная двусвязность
Отношение реберной двусвязности является отношением эквивалентности на вершинах.
|proof=
[[Файл:Rcon1.png|right|360px|thumb|]]
Пусть <tex>R</tex> - отношение реберной двусвязности.
''Доказательство:''
[[Файл:GumnoRcon2.png|right|480px360px|thumb|]] Пусть из <tex> u </tex> в <tex> v </tex> есть два реберно не пересекающихся пути. Их объединение будет реберно-простым циклом. Обозначим его за <tex> C </tex>.
Вершина <tex> w </tex> реберно двусвязна с <tex> v </tex>. Назовем эти пути <tex> P_1 </tex> и <tex> P_2 </tex>.
Пусть вершина <tex> a </tex> - пересечение <tex> P_1 </tex> с циклом<tex> C </tex>.Пусть вершина <tex> b </tex> - пересечение <tex> P_2 </tex> с циклом<tex> C </tex>.
Рассматриваем два пути <tex> wau </tex> и <tex> wbu </tex> таких, что части <tex> au </tex> и <tex> bu </tex> идут в разные стороны относительно часовой стрелки.
Наличие двух таких реберно не пересекающихся пути путей очевидно, а значит <tex> u </tex> и <tex> w </tex> реберно двусвязны.
}}
