Лапы и минимальные по включению барьеры в графе — различия между версиями

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

Версия 02:49, 14 декабря 2017

Определение:
Лапой (англ. paw) называется индуцированный подграф графа [math]G[/math], изоморфный двудольному графу [math]K_{1,\;3}[/math].
Лапа
Определение:
Центр лапы (англ. paw center) — вершина степени 3 в лапе.


Определение:
Минимальный по включению барьер (англ.minimum barrier) — барьер минимальной мощности.


Теорема:
Пусть [math]B[/math] - минимальный по включению барьер [math]G[/math], тогда каждая вершина [math]B[/math] - центр лапы в [math]G[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]x\in B[/math] не является центром лапы. Тогда [math]x[/math] смежна не более чем с двумя компонентами связности графа [math]G \setminus B[/math].
Обозначим [math]B' = B\setminus x[/math].
Найдём соотношение между [math]\mathrm{odd}(G\setminus B')\ [/math] и [math]\mathrm{odd}(G\setminus B)\ [/math].
Рассмотрим возможные случаи количества компонент связности в [math]G \setminus B[/math], с которыми смежна [math]x[/math], и посмотрим на их четности(компоненты в [math]B[/math] нас не интересуют).

  1. [math]x[/math] смежна с двумя компонентами связности [math]G \setminus B[/math].
    [math]x[/math] смежна с двумя компонентами связности из [math]G \setminus B[/math]
    .
    a) Одна четная, другая - нечетная. Тогда [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 [/math]
    b) Обе чётные : [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 [/math]
    c) Обе нечётные : [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 [/math]
  2. [math]x[/math] смежна с одной компонентой связности [math]G \setminus B[/math].
    a) Она чётная : [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 [/math]
    b) Она нечётная : [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 [/math]
  3. [math]x[/math] не смежна ни с какой компонентой связности [math]G \setminus B[/math] : [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 [/math]

Рассмотрев случаи, видим, что для любого из них выполнено : [math]\mathrm{odd}(G\setminus B')\ \geqslant \mathrm{odd}(G\setminus B)\ + 1 [/math]
[math]B[/math] — барьер [math] \Leftrightarrow \mathrm{odd}(G\setminus B) - |B| = \mathrm{def}(G) [/math]
Тогда [math]\mathrm{odd}(G\setminus B')\ \geqslant |B| - 1 + \mathrm{def}(G)[/math]
То есть [math]\mathrm{odd}(G\setminus B') - |B'|\ \geqslant \mathrm{def}(G)[/math]
Тогда возможны два случая:

  1. Если выполняется равенство [math]\mathrm{odd}(G\setminus B') - |B'|\ = \mathrm{def}(G)[/math], то, по определению [math]B'[/math] является барьером.
    Но [math]|B'| \lt |B| [/math], а значит, [math]B[/math] не является минимальным по включению барьером [math]\Rightarrow[/math] противоречие условию.
  2. Если [math]\mathrm{odd}(G\setminus B') - |B'|\ \gt \mathrm{def}(G)[/math], то
    [math]\mathrm{odd}(G\setminus B') - |B'|\ \gt \mathrm{def}(G) = \mathrm{odd}(G\setminus B) - |B|\[/math], что противоречит теореме Бержа.
В обоих случаях мы пришли к противоречию, значит, наше предположение неверно и [math]\forall x\in B[/math] является центром лапы в [math]G[/math].
[math]\triangleleft[/math]
Утверждение (D.P.Sumner, следствие из теоремы):
Пусть [math]G[/math] — связанный граф, не содержащий лапы, [math]v(G)[/math] чётно. Тогда [math]G[/math] имеет совершенное паросочетание.
[math]\triangleright[/math]

Пусть [math]B[/math] — минимальный по включению барьер графа [math]G[/math]. Тогда, по предыдущей теореме имеем [math]B = \varnothing [/math].
По условию [math]G[/math] — связный граф с чётным числом вершин [math]\Rightarrow [/math] [math]\mathrm{odd}(G\setminus \varnothing )\ = 0 [/math].

[math]B[/math] — барьер [math]\Leftrightarrow \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = \mathrm{def}(G) = 0 [/math]. Значит, количество вершин, не покрытых максимальным паросочетанием, равно 0, т.е. существует совершенное паросочетание.
[math]\triangleleft[/math]

См. также

Источники информации

  • Карпов В. Д. - Теория графов, стр 55