133
правки
Изменения
Нет описания правки
{{Определение
|id = paw|definition='''Лапой''' (англ. ''paw'') называется индуцированный подграф графа <tex>G</tex>, изоморфный двудольному графу <tex>K_{1,\;3}</tex>.}}[[Файл:Lapa.png|170px|thumb|left|Лапа]]
{{Определение
|id = paw center|definition='''Центр лапы''' (англ. ''paw center'') {{---}} вершина степени 3 в лапе.
}}
{{Определение
|id = minimum_barrier|definition='''Минимальный по включению [[Декомпозиция Эдмондса-Галлаи#barrier | барьер]] '''(англ.''minimum barrier'') {{---}} барьер минимальной мощности.
}}
|statement=Пусть <tex>B</tex> - минимальный по включению барьер <tex>G</tex>, тогда каждая вершина <tex>B</tex> - центр лапы в <tex>G</tex>.
|proof=Пусть <tex>x\in B</tex> не является центром лапы. Тогда <tex>x</tex> смежна не более чем с двумя компонентами связности графа <tex>G \setminus B</tex>.<br>
Обозначим <tex>B' = B\setminus x</tex>.<br>Найдём соотношение между <tex>\mathrm{odd}(G\setminus B')\ </tex> и <tex>\mathrm{odd}(G\setminus B)\ </tex> . <br>Рассмотрим возможные случаи количества компонент связности в <tex>G \setminus B</tex>, с которыми смежна <tex>x</tex>, и посмотрим на их четности(компоненты в <tex>B</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>
|statement=Пусть <tex>G</tex> {{---}} связанный граф, не содержащий лапы, <tex>v(G)</tex> чётно. Тогда <tex>G</tex> имеет [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание]].
|proof= Пусть <tex>B</tex> {{---}} минимальный по включению барьер графа <tex>G</tex>. Тогда, по предыдущей теореме имеем <tex>B = \varnothing </tex>.<br>
По условию <tex>G</tex> {{---}} связный граф с чётным числом вершин <tex>\Rightarrow </tex> <tex>\mathrm{odd}(G\setminus \varnothing )\ = 0 </tex> . <br>
<tex>B</tex> {{---}} барьер <tex>\Leftrightarrow \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = \mathrm{def}(G) = 0 </tex>. Значит, количество вершин, не покрытых [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#maximal_matching | максимальным паросочетанием]], равно 0, т.е. существует совершенное паросочетание.
}}
