84
правки
Изменения
м
Нет описания правки
|statement=Кубический граф, у которого нет [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| совершенного паросочетания]], содержит как минимум <tex>3</tex> моста. }}
Следствие из данной теоремы: для любого [[Отношение связности, компоненты связности| двусвязного ]] кубического графа существует совершенное паросочетание.
==Теорема Фринка (Frink)==
* компонента <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> следующим образом:
* если путь <tex> x - c - d - y </tex> <math>\in</math> <tex> C </tex>, <tex> x </tex> <math>\in</math> <tex> \{a, b\} </tex>, <tex> y </tex> <math>\in</math> <tex> \{e, f\} </tex>, удалим этот путь и добавим любой другой из <tex> x </tex> в <tex> y </tex> в <tex> G' </tex>, не содержащий <tex>r</tex> (такой путь всегда существует, так как <tex> x </tex> и <tex> y </tex> принадлежат некоторому циклу в <tex> G' </tex>),
* если путь <tex> a - c - b </tex> <math>\in</math> <tex> C </tex>, удалим этот путь и добавим любой другой из <tex> a </tex> в <tex> b </tex> в <tex> G' </tex>, не содержащий <tex>r</tex>,
