Викиконспекты - Вклад участника [ru]

Лапы и минимальные по включению барьеры в графе

2017-12-14T13:15:12Z

176.59.3.167:

{{Определение
|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'') {{---}} барьер минимальной мощности.
}}

{{Теорема
|id=th1
|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>. 
Обозначим <tex>B' = B\setminus x</tex>. 
Найдём соотношение между <tex>\mathrm{odd}(G\setminus B')\ </tex> и <tex>\mathrm{odd}(G\setminus B)\ </tex>. 
Рассмотрим возможные случаи количества компонент связности в <tex>G \setminus B</tex>, с которыми смежна <tex>x</tex>, и посмотрим на их четности(компоненты в <tex>B</tex> нас не интересуют). 
# <tex>x</tex> смежна с двумя компонентами связности <tex>G \setminus B</tex>.[[Файл:GraphsForLaps.png|300px|thumb|right|<tex>x</tex> смежна с двумя компонентами связности из <tex>G \setminus B</tex>]]. 
#:a) Одна четная, другая - нечетная. Тогда <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> 
#:b) Обе чётные : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> 
#:c) Обе нечётные : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> 
#<tex>x</tex> смежна с одной компонентой связности <tex>G \setminus B</tex>. 
#:a) Она чётная : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> 
#:b) Она нечётная : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> 
# <tex>x</tex> не смежна ни с какой компонентой связности <tex>G \setminus B</tex> : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> 
Рассмотрев случаи, видим, что для любого из них выполнено : <tex>\mathrm{odd}(G\setminus B')\ \geqslant \mathrm{odd}(G\setminus B)\ + 1 </tex> 
<tex>B</tex> {{---}} барьер <tex> \Leftrightarrow \mathrm{odd}(G\setminus B) - |B| = \mathrm{def}(G) </tex> 
Тогда <tex>\mathrm{odd}(G\setminus B')\ \geqslant |B| - 1 + \mathrm{def}(G)</tex> 
То есть <tex>\mathrm{odd}(G\setminus B') - |B'|\ \geqslant \mathrm{def}(G)</tex> 
Тогда возможны два случая:
#Если выполняется равенство <tex>\mathrm{odd}(G\setminus B') - |B'|\ = \mathrm{def}(G)</tex>, то, по определению <tex>B'</tex> является барьером. 
#:Но <tex>|B'| < |B| </tex>, а значит, <tex>B</tex> не является минимальным по включению барьером <tex>\Rightarrow</tex> противоречие условию. 
#Если <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G)</tex>, то 
#:<tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G) = \mathrm{odd}(G\setminus B) - |B|\</tex>, что противоречит [[Декомпозиция Эдмондса-Галлаи#Th_Berge| теореме Бержа]]. 
В обоих случаях мы пришли к противоречию, значит, наше предположение неверно и <tex>\forall x\in B</tex> является центром лапы в <tex>G</tex>.
}}
{{Утверждение
|id=proposal1.
|author=D.P.Sumner
|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>. 
По условию <tex>G</tex> {{---}} связный граф с чётным числом вершин <tex>\Rightarrow </tex> <tex>\mathrm{odd}(G\setminus \varnothing )\ = 0 </tex>. 
<tex>B</tex> {{---}} барьер <tex>\Leftrightarrow \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = \mathrm{def}(G) = 0 </tex>. Значит, количество вершин, не покрытых [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#maximal_matching | максимальным паросочетанием]], равно 0, т.е. существует совершенное паросочетание.
}}

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

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

== Источники информации ==
* Карпов В. Д. - Теория графов, стр 55

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

Лапы и минимальные по включению барьеры в графе

2017-12-13T20:09:36Z

176.59.3.167:

{{Определение
|definition='''Лапой''' называется индуцированный подграф графа <tex>G</tex>, изоморфный двудольному графу <tex>K_{1,\;3}</tex>
}}
{{Определение
|definition='''Центр лапы''' {{---}} вершина степени 3 в лапе
}}
{{Определение
|definition='''Минимальный по включению [[Декомпозиция Эдмондса-Галлаи#def2 | барьер]] ''' {{---}} барьер минимальной мощности
}}

{{Теорема
|id=th1
|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>. 
Обозначим <tex>B' = B\setminus x</tex> 
Найдём соотношение между <tex>\mathrm{odd}(G\setminus B')\ </tex> и <tex>\mathrm{odd}(G\setminus B)\ </tex> 
Рассмотрим возможные случаи количества компонент связности в <tex>G \setminus B</tex>, с которыми смежна <tex>x</tex>, и посмотрим на их четности(компоненты в <tex>B</tex> нас не интересуют) 
# <tex>x</tex> смежна с двумя компонентами связности <tex>G \setminus B</tex>. 
#:a) Одна четная, другая - нечетная. Тогда <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> 
#:b) Обе чётные : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> 
#:c) Обе нечётные : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> 
#<tex>x</tex> смежна с одной компонентой связности <tex>G \setminus B</tex>. 
#:a) Она чётная : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> 
#:b) Она нечётная : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> 
# <tex>x</tex> не смежна ни с какой компонентой связности <tex>G \setminus B</tex> : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> 
Рассмотрев случаи, видим, что для любого из них выполнено : <tex>\mathrm{odd}(G\setminus B')\ \geqslant \mathrm{odd}(G\setminus B)\ + 1 </tex> 
<tex>B</tex> {{---}} барьер <tex> \Leftrightarrow \mathrm{odd}(G\setminus B) - |B| = \mathrm{def}(G) </tex> 
Тогда <tex>\mathrm{odd}(G\setminus B')\ \geqslant |B| - 1 + \mathrm{def}(G)</tex> 
То есть <tex>\mathrm{odd}(G\setminus B') - |B'|\ \geqslant \mathrm{def}(G)</tex> 
Тогда возможны два случая:
#Если выполняется равенство <tex>\mathrm{odd}(G\setminus B') - |B'|\ = \mathrm{def}(G)</tex>, то, по определению <tex>B'</tex> является барьером. 
#:Но <tex>|B'| < |B| </tex>, а значит, <tex>B</tex> не является минимальным по включению барьером <tex>\Rightarrow</tex> противоречие условию. 
#Если <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G)</tex>, то 
#:<tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G) = \mathrm{odd}(G\setminus B) - |B|\</tex>, что противоречит [[Декомпозиция Эдмондса-Галлаи#def1 | теореме Бержа]]. 
В обоих случаях мы пришли к противоречию, значит, наше предположение неверно и <tex>\forall x\in B</tex> является центром лапы в <tex>G</tex>.
}}
{{Утверждение
|id=proposal1.
|author=D.P.Sumner
|about=следствие из теоремы
|statement=Пусть <tex>G</tex> {{---}} связанный граф, не содержащий лапы, <tex>v(G)</tex> чётно. Тогда <tex>G</tex> имеет [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание]].
|proof=доказательство (необязательно)
}}

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

* [[Использование обхода в глубину для поиска цикла]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]

== Источники информации ==
* Карпов В. Д. - Теория графов, стр 55

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