Изменения

Перейти к: навигация, поиск

Мост, эквивалентные определения

16 байт убрано, 00:15, 28 октября 2010
м
Нет описания правки
<tex>(3) \Rightarrow (1)</tex> Пусть <tex>(a, b) = x</tex>. Пусть ребро <tex>x</tex> не является мостом по определению (1).
Тогда между вершинами <tex>a</tex> и <tex>b</tex> есть простой путь <tex>P : P \land x = \varnothing</tex>. Составим такой путь <tex>Q</tex>, что <tex>Q = ((u \rightsquigarrow a )</tex> o <tex> \circ P </tex> o <tex>\circ (b \rightsquigarrow w)) </tex>. Сделаем путь <tex>Q</tex> [[Теорема о существовании простого пути в случае существования пути|простым]]. Получим простой путь <tex>(u \rightsquigarrow w)</tex>, не проходящий по ребру <tex>x</tex>. Противоречие.
}}
205
правок

Навигация