133
правки
Изменения
Нет описания правки
|id = paw
|neat = 1
|definition='''Лапой''' (англ. ''paw'') называется индуцированный подграф графа <tex>G</tex>, [[Основные определения теории графов#isomorphic_graphs | изоморфный]] [[Основные определения теории графов#defBiparateGraph | двудольному]] графу <tex>K_{1,\;3}</tex>.
}} [[Файл:Lapa.png|180px|thumb|right|Лапа]]
|id = paw_center
|neat = 1
|definition='''Центром лапы''' (англ. ''paw center'') называется вершина [[Основные определения теории графов#def_graph_degree_1| степени]] три в лапе.
}}
|neat = 1
|id = minimum_barrier
|definition='''Минимальным по включению [[Декомпозиция Эдмондса-Галлаи#barrier | барьером]] '''(англ.''minimum barrier'') называется барьер минимальной мощности.
}}
{{Теорема
|id=theorem1
|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>
Найдём соотношение между [[Теорема Татта о существовании полного паросочетания#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> нас не интересуют).<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>
#<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>
# <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>
