Редактирование: Декомпозиция Эдмондса-Галлаи

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
В этом направлении много усилий приложили Вильям Томас '''Татт''' (''William Thomas Tutte''), Клод '''Берж''' (''Claude Berge''), Джек '''Эдмондс''' (''Jack Edmonds'') и Тибор '''Галлаи''' (''Tibor Gallai'').
+
В этом направлении много усилий приложили Вильям Томас '''Татт''' (''William Thomas Tutte''), Клауд '''Берж''' (''Claude Brege''), Джек '''Эдмондс''' (''Jack Edmonds'') и Тибор '''Галлаи''' (''Tibor Gallai'').
 
{{Определение  
 
{{Определение  
|id = deficit
 
 
|definition=
 
|definition=
 
'''Дефицитом''' (англ. ''deficit'') графа <tex>G</tex> мы будем называть величину: <br>
 
'''Дефицитом''' (англ. ''deficit'') графа <tex>G</tex> мы будем называть величину: <br>
Строка 19: Строка 18:
  
 
{{Теорема
 
{{Теорема
|id = theorem_Tatt_Berge
 
 
|about=Татта-Бержа
 
|about=Татта-Бержа
 
|statement=
 
|statement=
Строка 59: Строка 57:
 
|neat = 1
 
|neat = 1
 
|definition=
 
|definition=
Структурные единицы декопозиции:
+
Основные определения:
 
# <tex>D(G) = \{v \in V \mid </tex> существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]], не покрывающее <tex> v\}</tex>
 
# <tex>D(G) = \{v \in V \mid </tex> существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]], не покрывающее <tex> v\}</tex>
 
# <tex>A(G) = N(D(G)) \setminus D(G)</tex>
 
# <tex>A(G) = N(D(G)) \setminus D(G)</tex>
Строка 72: Строка 70:
  
 
{{Теорема
 
{{Теорема
|id = theorem_Gallai
 
 
|about=Галлаи
 
|about=Галлаи
 
|statement=
 
|statement=
Строка 81: Строка 78:
  
 
{{Лемма
 
{{Лемма
|id = stability_lemma
 
 
|about= Галлаи, о стабильности (англ. ''stability lemma'')
 
|about= Галлаи, о стабильности (англ. ''stability lemma'')
 
|statement=
 
|statement=
Строка 90: Строка 86:
 
# <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
 
# <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
 
|proof=
 
|proof=
Для начала докажем, что <tex>D(G - a) = D(G)</tex>. <br>
+
Достаточно доказать, что <tex>D(G - a) = D(G)</tex>. <br>
 
[[Файл: Gallai-lema-a.png|150px|thumb|right|Случай '''а''']]
 
[[Файл: Gallai-lema-a.png|150px|thumb|right|Случай '''а''']]
 
[[Файл: Gallai-lema-b.png|150px|thumb|right|Случай '''b''']]
 
[[Файл: Gallai-lema-b.png|150px|thumb|right|Случай '''b''']]
Строка 112: Строка 108:
 
Таким образом, наше предположение невозможно и <tex>D(G - a) \subset D(G)</tex>.
 
Таким образом, наше предположение невозможно и <tex>D(G - a) \subset D(G)</tex>.
 
А значит, <tex>D(G - a) = D(G)</tex>.
 
А значит, <tex>D(G - a) = D(G)</tex>.
 
 
Так как <tex>D(G - a) = D(G)</tex>, то все вершины, которые были соседями <tex>D(G)</tex>, таковыми и остались. Однако, по условию <tex> a \in A(G)</tex>, значит <tex>A(G - a) = A(G) \setminus \{a\}</tex>.
 
 
 
Так же заметим, что <tex>C(G - a) = V(G - a) \setminus (D(G - a) \cup A(G - a)) = V(G - a) \setminus (D(G) \cup (A(G) \setminus \{a\}))</tex><tex> = V(G) \setminus (D(G) \cup A(G)) = C(G)</tex>
 
 
 
Наконец, так как <tex> a \in A(G)</tex>, то все максимальные паросочетания в <tex>G</tex> включали <tex>a</tex>. Следовательно, <tex>\alpha (G - a) < \alpha (G)</tex>. Заметим, что, взяв любое максимальное паросочетания в <tex>G</tex> и удалив ребро инцидентное <tex>a</tex>, мы получим паросочетание <tex>M'</tex>, которое на 1 меньше исходного, при этом <tex>M' \in E(G - a)</tex>. В свою очередь, это самое большое паросочетание, которое мы могли теоретически получить в <tex>G - a</tex>. Следовательно, <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
 
 
}}
 
}}
  
  
 
{{Теорема
 
{{Теорема
|id = theorem_Gallai_Edmonds
 
 
|about = Галлаи, Эдмондс
 
|about = Галлаи, Эдмондс
 
|statement=
 
|statement=
Строка 159: Строка 145:
 
|id = barier_struct1
 
|id = barier_struct1
 
|about = о связи барьера с <tex>D(G)</tex>
 
|about = о связи барьера с <tex>D(G)</tex>
|statement= Для любого барьера <tex>B</tex> графа <tex>G</tex> верно, что <tex>B\cap D(G) = \varnothing</tex>
+
|statement= Для любого барьера графа <tex>B</tex> верно, что <tex>B\cap D(G) = \varnothing</tex>
|proof= Рассмотрим <tex>U_{1}, U_{2},  \ldots U_{n}</tex> {{---}} нечётные компоненты связанности <tex>G \setminus B</tex>, <tex>\ M</tex> {{---}} максимальное паросочетание в <tex>G</tex>. <tex>\forall\ U_{i}\ \exists x \in U_{i}: x</tex> не покрыта <tex>\ M</tex> или <tex>xv \in M \land v \in B</tex>. Всего графе не покрыто хотя бы <tex>odd(G\setminus B) - |B|</tex> вершин. Однако, так как <tex>B</tex> {{---}} барьер, непокрыто '''ровно''' столько вершин. Следовательно, любое максимальное паросочетание не покрывает только вершины из <tex>G \setminus B</tex>, а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из <tex>D(G)</tex> не могла оказаться в барьере.
+
|proof= Рассмотрим <tex>U_{1}, U_{2},  \ldots U_{n}</tex> {{---}} нечётные компоненты связанности <tex>G \setminus B</tex>, <tex>\ M</tex> {{---}} максимальное паросочетание в <tex>G</tex>. <tex>\forall\ U_{i}\ \exists x \in U_{i}: x</tex> не покрыта <tex>\ M</tex> или <tex>xv \in M \land v \in B</tex>. Всего графе не покрыто хотя бы <tex>odd(G\setminus B) - |B|</tex> вершин. Однако так как <tex>B</tex> {{---}} барьер, непокрыто '''ровно''' столько вершин. Следовательно любое максимальное паросочетание не покрывает только вершины из <tex>G \setminus B</tex>, а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из <tex>D(G)</tex> не могла оказаться в барьере.
 
}}
 
}}
  
Строка 167: Строка 153:
 
|about=Следствие из леммы
 
|about=Следствие из леммы
 
|statement=В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами <tex>G \setminus B</tex>
 
|statement=В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами <tex>G \setminus B</tex>
|proof=Так как для барьера <tex>B</tex> верно, что <tex>odd(G\setminus B) - |B|=def(G) \geqslant 0</tex>, то ровно <tex>|B|</tex> вершин из нечётных компонент <tex>G \setminus B</tex> покрыты рёбрами <tex>xv \in M \land v \in B</tex>
+
|proof=Так как в барьере <tex>odd(G\setminus B) - |B|=def(G) \geqslant 0</tex>, то ровно <tex>|B|</tex> вершин из нечётных компонент <tex>G \setminus B</tex> покрыты рёбрами <tex>xv \in M \land v \in B</tex>
 
}}
 
}}
  
Строка 174: Строка 160:
 
|about = о дополнении барьера
 
|about = о дополнении барьера
 
|statement= Пусть <tex>x\in A(G)\cup C(G),\ G'=G\setminus x,\ B'</tex> {{---}} барьер графа <tex>G'</tex>. Тогда <tex>B=B'\cup x</tex> {{---}} барьер графа <tex>G</tex>
 
|statement= Пусть <tex>x\in A(G)\cup C(G),\ G'=G\setminus x,\ B'</tex> {{---}} барьер графа <tex>G'</tex>. Тогда <tex>B=B'\cup x</tex> {{---}} барьер графа <tex>G</tex>
|proof= Так как <tex>x \notin D(G)</tex>, то для любого максимального паросочетания <tex>M: x \in M</tex>. Следовательно, <tex>|M'| = |M| - 1</tex>, где <tex>M'</tex> {{---}} максимальное паросочетание в <tex>G'</tex>.
+
|proof= Так как <tex>x \notin D(G)</tex>, то <tex>\forall\ M</tex> {{---}} максимального паросочетания в <tex>G : x \in M</tex>. Следовательно <tex>|M'| = |M| - 1</tex>, где <tex>M'</tex> {{---}} максимальное паросочетание в <tex>G'</tex>.
  
 
<tex>def(G') = (|V| - 1)- 2 \cdot |M'| = |V| - 2 \cdot |M| + 1 = def(G) + 1</tex>  
 
<tex>def(G') = (|V| - 1)- 2 \cdot |M'| = |V| - 2 \cdot |M| + 1 = def(G) + 1</tex>  
Строка 191: Строка 177:
 
== См. также ==
 
== См. также ==
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Теорема Татта о существовании полного паросочетания]]
* [[Лапы и минимальные по включению барьеры в графе]]
 
* [[Пересечение всех максимальных по включению барьеров]]
 
  
 
== Источники информации==
 
== Источники информации==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)