84
правки
Изменения
Нет описания правки
|id=th1.
|author=Петерсон
|statement=Кубический граф, у которого нет совершенного паросочетания, содержит как минимум <tex>3 </tex> моста. }}
==Следствие теоремы Петерсона==
* компонента <tex>B</tex> соединена с <tex>E</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>
* компонента <tex>A</tex> соединена с <tex>B</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>
Во всех трёх случаях если <tex>G(V - {c, d})</tex> расширить рёбрами <tex>(a, f), (b, e)</tex> (получим граф <tex>G'</tex>), добавленные рёбра будут лежать на некотором цикле в <tex>G'</tex> (рисунок <tex>4</tex>). Так же, для любой пары вершин <tex>u, v</tex> <math>\in</math><tex>{a, b, e, f}</tex> существует цикл в <tex>G'</tex>, содержащий данные вершины. Чтобы доказать, что <tex>G'</tex> двусвязен, нужно показать, что каждое ребро <tex>r</tex> из <tex>G'</tex> лежит на некотором цикле в <tex>G'</tex>. Пусть цикл <tex>C</tex> в <tex>G</tex> содержит <tex>r</tex> (такой цикл существует, так как <tex>G</tex> двусвязен). Если <tex>C</tex> не проходит через вершины <tex>c, d</tex> тогда <tex>C</tex> так же является циклом в <tex>G'</tex>, иначе построим цикл <tex>C'</tex> графа <tex>G'</tex> из <tex>C</tex> следующим образом:
}}
