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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
}}
 
}}
 
{{Определение
 
{{Определение
|definition='''Минимальный по включению [[Декомпозиция Эдмондса-Галлаи#def1 | барьер]] ''' {{---}} барьер минимальной мощности
+
|definition='''Минимальный по включению [[Декомпозиция Эдмондса-Галлаи#def2 | барьер]] ''' {{---}} барьер минимальной мощности
 
}}
 
}}
  
Строка 28: Строка 28:
 
Тогда <tex>\mathrm{odd}(G\setminus B')\ \geqslant |B| - 1 + \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'|\ \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>, что противоречит [[Декомпозиция Эдмондса-Галлаи#def1 | теореме Бержа]]. <br>
 
}}
 
}}

Версия 21:56, 13 декабря 2017

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


Определение:
Центр лапы — вершина степени 3 в лапе


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


Теорема:
Пусть [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].
    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]
Тогда, если выполняется равенство [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] противоречие условию.
Если [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]\triangleleft[/math]