133
правки
Изменения
Нет описания правки
Для этого рассмотрим всевозможные случаи количества компонент связности в графе <tex>G \setminus B</tex>, с которыми смежна <tex>x</tex>, и посмотрим на их четности (компоненты в <tex>B</tex>, с которыми смежна <tex>x</tex>, нас не интересуют).<br>
# <tex>x</tex> смежна с двумя компонентами связности графа <tex>G \setminus B</tex>.[[Файл:GraphsForLaps.png|300px|thumb|right|<tex>x</tex> смежна с двумя компонентами связности из <tex>G \setminus B</tex>]]<br>
#: a) Одна компонента четнаячётная, другая {{---}} нечетная. Тогда <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> <br>
#: b) Обе компоненты чётные: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> <br>
#: c) Обе компоненты нечётные: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> <br>
==См. также==
* [[Декомпозиция Эдмондса-Галлаи]]* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]* [[Теорема Татта о существовании полного паросочетания]]
== Источники информации ==
* Карпов Д. В. {{- --}} Теория графов, стр 55
[[Категория: Алгоритмы и структуры данных]][[Категория:Задача о паросочетании]]
