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

Материал из Викиконспекты
Перейти к: навигация, поиск
(definition fixed?)
(не показано 40 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|id = paw
+
|id = claw
|definition='''Лапой''' (англ. ''paw'') называется индуцированный подграф графа <tex>G</tex>, изоморфный двудольному графу <tex>K_{1,\;3}</tex>.
+
|neat = 1
}} [[Файл:Lapa.png|170px|thumb|left|Лапа]]
+
|definition = '''Лапой''' (англ. ''claw'') называется индуцированный подграф графа <tex>G</tex>, [[ Основные определения теории графов#isomorphic_graphs | изоморфный]] [[ Основные определения теории графов#defBiparateGraph | двудольному ]] графу <tex>K_{1, 3}</tex>.
 +
}} [[ Файл:Lapa.png|180px|thumb|right|Лапа ]]
 +
                                                                                                                                         
 +
                                                                                               
 +
 
 +
                                                       
 +
                                                                                                                                         
 +
                                                                                                                                     
 
{{Определение
 
{{Определение
|id = paw center
+
|id = claw_center
|definition='''Центр лапы''' (англ. ''paw center'') {{---}} вершина степени 3 в лапе.
+
|neat = 1
 +
|definition ='''Центром лапы''' (англ. ''claw center'') называется вершина [[ Основные определения теории графов#def_graph_degree_1 | степени ]] три в лапе.
 
}}
 
}}
 +
                                                                                                                                   
 +
                                                                                                                               
 +
 +
 +
 
{{Определение
 
{{Определение
 
|id = minimum_barrier
 
|id = minimum_barrier
|definition='''Минимальный по включению [[Декомпозиция Эдмондса-Галлаи#barrier | барьер]] '''(англ.''minimum barrier'') {{---}} барьер минимальной мощности.
+
|neat = 1
 +
|definition = '''Минимальным по включению [[ Декомпозиция Эдмондса-Галлаи#barrier | барьером ]] '''(англ.''minimal barrier'') называется барьер, который перестанет быть барьером при исключении из него любой вершины.
 
}}
 
}}
 +
 +
                                                                                                                                         
 +
                                                                                                         
 +
                             
  
 
{{Теорема
 
{{Теорема
|id=th1
+
|id = theorem_about_claw
|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> смежна не более чем с двумя [[Отношение связности, компоненты связности#def2 | компонентами связности]] графа <tex>G \setminus B</tex>. <br>  
Обозначим <tex>B' = B\setminus x</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>
+
Найдём соотношение между [[ Теорема Татта о существовании полного паросочетания#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>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>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>
+
#:* Одна компонента чётная, другая {{---}} нечетная. Тогда <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>\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>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br>
#<tex>x</tex> смежна с одной компонентой связности <tex>G \setminus B</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>
+
#:* Эта компонента чётная: <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>\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>x</tex> не смежна ни с какой компонентой связности графа <tex>G \setminus B</tex>. <br>
Рассмотрев случаи, видим, что для любого из них выполнено : <tex>\mathrm{odd}(G\setminus B')\ \geqslant \mathrm{odd}(G\setminus B)\ - 1 </tex> <br>
+
#: <tex>\mathrm{odd}(G\setminus B')\ = \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 \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br>
Тогда <tex>\mathrm{odd}(G\setminus B')\ \geqslant |B| - 1 + \mathrm{def}(G)</tex><br>  
+
<tex>B</tex> {{---}} барьер <tex> \Leftrightarrow \mathrm{odd}(G\setminus B) - |B| = \mathrm{def}(G) </tex>. <br>
То есть <tex>\mathrm{odd}(G\setminus B') - |B'|\ \geqslant \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> \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>|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)</tex>, то есть <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{odd}(G\setminus B) - |B|\</tex>. <br>
#:<tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G) = \mathrm{odd}(G\setminus B) - |B|\</tex>, что противоречит [[Декомпозиция Эдмондса-Галлаи#Th_Berge| теореме Бержа]]. <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>.
 
В обоих случаях мы пришли к противоречию, значит, наше предположение неверно и <tex>\forall x\in B</tex> является центром лапы в <tex>G</tex>.
 
}}
 
}}
 +
 
{{Утверждение  
 
{{Утверждение  
|id=proposal1.
+
|id = proposal1  
|author=D.P.Sumner, M.Las Vergnas
+
|author = D.P.Sumner, M.Las Vergnas
|about=следствие из теоремы
+
|about = следствие из теоремы
|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{def}(G) = \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = 0 </tex>. Значит, количество вершин, не покрытых [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#maximal_matching | максимальным паросочетанием]], равно 0, т.е. существует совершенное паросочетание.
+
<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
+
* Карпов Д. В. {{---}} Теория графов, стр 55
 +
*  Ловас Л., Пламмер М. {{---}} Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии, стр 165-166
  
[[Категория: Алгоритмы и структуры данных]]
+
[[ Категория: Алгоритмы и структуры данных ]]
[[Категория:Задача о паросочетании]]
+
[[ Категория: Задача о паросочетании ]]

Версия 17:27, 24 декабря 2017

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




Определение:
Центром лапы (англ. claw center) называется вершина степени три в лапе.




Определение:
Минимальным по включению барьером (англ.minimal 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}[/math] [math](G\setminus B')\ [/math] и [math]\mathrm{odd}(G\setminus B)\ [/math].
Для этого рассмотрим всевозможные случаи количества компонент связности в графе [math]G \setminus B[/math], с которыми смежна [math]x[/math], и посмотрим на их четности (компоненты в [math]B[/math], с которыми смежна [math]x[/math], нас не интересуют).

  1. [math]x[/math] смежна с двумя компонентами связности графа [math]G \setminus B[/math].
    [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')\ = \mathrm{odd}(G\setminus B)\ + 1 [/math].
    • Обе компоненты нечётные: [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 [/math].
  2. [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')\ = \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{odd}(G\setminus B) - |B|\[/math].
    Тогда, по теореме Бержа, [math]\mathrm{def}(G) \ne \mathrm{odd}(G\setminus B) - |B|\[/math] [math]\Rightarrow[/math] противоречие.
В обоих случаях мы пришли к противоречию, значит, наше предположение неверно и [math]\forall x\in B[/math] является центром лапы в [math]G[/math].
[math]\triangleleft[/math]
Утверждение (D.P.Sumner, M.Las Vergnas, следствие из теоремы):
Пусть [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{def}(G) = \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = 0 [/math]. Значит, количество вершин, не покрытых максимальным паросочетанием , равно [math]0[/math], то есть в [math]G[/math] существует совершенное паросочетание.
[math]\triangleleft[/math]

См. также

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

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