133
правки
Изменения
Нет описания правки
|id = paw
|neat = 1
|definition = '''Лапой''' (англ. ''paw'') называется индуцированный подграф графа <tex>G</tex>, [[Основные определения теории графов#isomorphic_graphs | изоморфный]] [[Основные определения теории графов#defBiparateGraph | двудольному]] графу <tex>K_{1,\;3}</tex>.}} [[Файл:Lapa.png|180px|thumb|right|Лапа]]
Найдём соотношение между [[ Теорема Татта о существовании полного паросочетания#odd | <tex>\mathrm{odd}</tex> ]]<tex>(G\setminus B')\ </tex> и <tex>\mathrm{odd}(G\setminus B)\ </tex>. <br>
Для этого рассмотрим всевозможные случаи количества компонент связности в графе <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>
#: 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>
# <tex>x</tex> не смежна ни с какой компонентой связности графа <tex>G \setminus B</tex>: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex>. <br>
Рассмотрев случаи, видим, что для любого из них выполнено: <tex>\mathrm{odd}(G\setminus B')\ \geqslant \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br>
<tex>B</tex> {{---}} барьер <tex> \Leftrightarrow \mathrm{odd}(G\setminus B) - |B| = \mathrm{def}(G) </tex>. <br>
То есть <tex> \mathrm{odd}(G\setminus B') - |B'|\ \geqslant \mathrm{def}(G) </tex>. <br>
Тогда возможны два случая:
#Если выполняется равенство <tex> \mathrm{odd}(G\setminus B') - |B'|\ = \mathrm{def}(G) </tex>, то, по определению, <tex>B'</tex> является барьером. <br>#:Но <tex>|B'| < |B| </tex>, а значит, <tex>B</tex> не является минимальным по включению барьером <tex>\Rightarrow</tex> противоречие условию теоремы. <br>#Если <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G)</tex>, то <br>#:<tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G) = \mathrm{odd}(G\setminus B) - |B|\</tex>, что противоречит [[ Декомпозиция Эдмондса-Галлаи#Th_Berge| теореме Бержа ]]. <br>
В обоих случаях мы пришли к противоречию, значит, наше предположение неверно и <tex>\forall x\in B</tex> является центром лапы в <tex>G</tex>.
}}
