Просмотр исходного текста страницы Лапы и минимальные по включению барьеры в графе

{{Определение
|id = claw
|neat = 1 
|definition = '''Лапой''' (англ. ''claw'') называется индуцированный подграф графа <tex>G</tex>, [[ Основные определения теории графов#isomorphic_graphs | изоморфный]] [[ Основные определения теории графов#defBiparateGraph | двудольному ]] графу <tex>K_{1, 3}</tex>.
}} [[ Файл:Lapa.png|180px|thumb|right|Лапа ]]
                                                                                                                                           
                                                                                                 

                                                        
                                                                                                                                          
                                                                                                                                      
{{Определение
|id = claw_center
|neat = 1 
|definition ='''Центром лапы''' (англ. ''claw center'') называется вершина [[ Основные определения теории графов#def_graph_degree_1 | степени ]] три в лапе.
}}
                                                                                                                                    
                                                                                                                                 



{{Определение
|id = minimum_barrier
|neat = 1 
|definition = '''Минимальным по включению [[ Декомпозиция Эдмондса-Галлаи#barrier | барьером ]] '''(англ.''minimal barrier'') называется барьер, который перестанет быть барьером при исключении из него любой вершины.
}}

                                                                                                                                          
                                                                                                          
                               

{{Теорема
|id = theorem_about_claw
|statement = Пусть <tex>B</tex> {{---}} минимальный по включению барьер графа <tex>G</tex>, тогда каждая вершина <tex>B</tex> {{---}} центр лапы в <tex>G</tex>.
|proof = Предположим, что <tex>x\in B</tex> не является центром лапы. Тогда <tex>x</tex> смежна не более чем с двумя [[Отношение связности, компоненты связности#def2 | компонентами связности]] графа <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>, с которыми смежна <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>
#:* Одна компонента чётная, другая {{---}} нечетная. Тогда <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br>
#:* Обе компоненты чётные: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex>. <br>
#:* Обе компоненты нечётные: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br>
#<tex>x</tex> смежна с одной компонентой связности графа <tex>G \setminus B</tex>. <br>
#:* Эта компонента чётная: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex>. <br>
#:* Эта компонента нечётная: <tex>\mathrm{odd}(G\setminus B')\  =  \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br>
#  <tex>x</tex> не смежна ни с какой компонентой связности графа <tex>G \setminus B</tex>. <br>
#: <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')\  \geqslant  |B| - 1 + \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>, то есть <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{odd}(G\setminus B) - |B|\</tex>. <br>
#: Тогда, по [[ Декомпозиция Эдмондса-Галлаи#Th_Berge| теореме Бержа]], <tex>\mathrm{def}(G) \ne \mathrm{odd}(G\setminus B) - |B|\</tex> <tex>\Rightarrow</tex> противоречие. <br>
В обоих случаях мы пришли к противоречию, значит, наше предположение неверно и <tex>\forall x\in B</tex> является центром лапы в <tex>G</tex>.
}}

{{Утверждение 
|id = proposal1   
|author = D.P.Sumner, M.Las Vergnas
|about = следствие из теоремы
|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{def}(G) = \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = 0 </tex>. Значит, количество вершин, не покрытых [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#maximal_matching | максимальным паросочетанием ]], равно <tex>0</tex>, то есть в <tex>G</tex> существует совершенное паросочетание.
}}

==См. также==

*  [[ Декомпозиция Эдмондса-Галлаи ]]
*  [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях ]]
*  [[ Теорема Татта о существовании полного паросочетания ]]
*  [[ Теорема Самнера — Лас Вергнаса ]]

== Источники информации ==
*  Карпов Д. В. {{---}} Теория графов, стр 55
*  Ловас Л., Пламмер М. {{---}} Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии, стр 165-166

[[ Категория: Алгоритмы и структуры данных ]]
[[ Категория: Задача о паросочетании ]]