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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 94: Строка 94:
 
[[Файл: Gallai-lema-b.png|150px|thumb|right|Случай '''b''']]
 
[[Файл: Gallai-lema-b.png|150px|thumb|right|Случай '''b''']]
 
[[Файл: Gallai-lema-с.png|150px|thumb|right|Случай '''c''']]
 
[[Файл: Gallai-lema-с.png|150px|thumb|right|Случай '''c''']]
# Покажем, что <tex>D(G - a) \supset D(G)</tex> : <br>
+
# покажем, что <tex>D(G - a) \supset D(G)</tex> : <br>
 
#:Пусть <tex>u \in D(G)</tex>. Тогда существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] <tex>M_u</tex> графа <tex>G</tex>, не покрывающее <tex>u</tex>. Поскольку любое максимальное паросочетание графа <tex>G</tex> покрывает <tex>a</tex>, то <tex> \alpha (G - a) = \alpha (G) - 1 </tex> и более того, если, для некоторой вершины <tex>x \in D(G)</tex>, <tex>ax \in M_u</tex>, то <tex>M_u \setminus {ax} </tex> {{---}}  максимальное паросочетание графа <tex> G - a </tex>, не покрывающее <tex> u </tex>. Таким образом, <tex>D(G - a) \supset D(G) </tex>. <br>
 
#:Пусть <tex>u \in D(G)</tex>. Тогда существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] <tex>M_u</tex> графа <tex>G</tex>, не покрывающее <tex>u</tex>. Поскольку любое максимальное паросочетание графа <tex>G</tex> покрывает <tex>a</tex>, то <tex> \alpha (G - a) = \alpha (G) - 1 </tex> и более того, если, для некоторой вершины <tex>x \in D(G)</tex>, <tex>ax \in M_u</tex>, то <tex>M_u \setminus {ax} </tex> {{---}}  максимальное паросочетание графа <tex> G - a </tex>, не покрывающее <tex> u </tex>. Таким образом, <tex>D(G - a) \supset D(G) </tex>. <br>
 
#покажем, что <tex> D(G - a) \subset D(G)</tex>: <br>
 
#покажем, что <tex> D(G - a) \subset D(G)</tex>: <br>
Строка 144: Строка 144:
 
#:Это означает, что не существует рёбер, соединяющих вершины из <tex>C(G - A)</tex> и <tex>D(G - A)</tex>. Каждое максимальное паросочетание <tex>M'</tex> графа <tex>G - A</tex> покрывает все вершины множества <tex>C(G)</tex>, поэтому <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex>. Тем самым, мы доказали пункт <tex>1)</tex>.
 
#:Это означает, что не существует рёбер, соединяющих вершины из <tex>C(G - A)</tex> и <tex>D(G - A)</tex>. Каждое максимальное паросочетание <tex>M'</tex> графа <tex>G - A</tex> покрывает все вершины множества <tex>C(G)</tex>, поэтому <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex>. Тем самым, мы доказали пункт <tex>1)</tex>.
 
#:
 
#:
# Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U_1\ldots U_n</tex> {{---}} компоненты связности графа <tex>G - A</tex>. Для любой вершины <tex>u \in U_i</tex> существует максимальное паросочетание <tex>M_u</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. Так как <tex>U_i</tex> {{---}} компонента связности графа <tex>G - A</tex>, паросочетание <tex>M_u</tex> содержит максимальное паросочетание графа <tex>D_i</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, <tex> \alpha (D_i) = \alpha (D_i - u) </tex> и по теореме Галлаи (мы получаем, что граф <tex>D_i</tex> {{---}} фактор-критический.
+
# Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U_1\ldots U_n</tex> {{---}} компоненты связности графа <tex>G - A</tex>. Для любой вершины <tex>u \in U_i</tex> существует максимальное паросочетание <tex>M_u</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. Так как <tex>U_i</tex> {{---}} компонента связности графа <tex>G - A</tex>, паросочетание <tex>M_u</tex> содержит максимальное паросочетание графа <tex>D_i</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, <tex> \alpha (D_i) = \alpha (D_i - u) </tex> и по теореме Галлаи (выше) мы получаем, что граф <tex>D_i</tex> {{---}} фактор-критический.
 
#:
 
#:
 
# Пусть <tex>M</tex> {{---}} максимальное паросочетание графа <tex>G</tex>, а <tex>M'</tex> получено из <tex>M</tex> удалением всех рёбер, инцидентных вершинам множества <tex>A</tex>. Тогда <tex>|M'| \geqslant |M| - |A|</tex> и по формуле <tex> \alpha (G - A) = \alpha (G) - |A|</tex> понятно, что <tex>M'</tex> {{---}} максимальное паросочетание графа <tex>G - A</tex>. Более того, из <tex> \alpha (G - A) = \alpha (G) - |A|</tex> следует <tex>|M'| = |M| - |A|</tex>, а значит, все вершины множества <tex>A</tex> покрыты в <tex>M</tex> различными рёбрами. Так как <tex>M'</tex> {{---}} максимальное паросочетание графа <tex>G - A</tex>, то по пунктам <tex>1)</tex> и <tex>2)</tex> очевидно, что <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex> и почти совершенные паросочетания фактор-критических графов <tex>D_1\ldots D_n</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U_1\ldots U_n</tex>.  
 
# Пусть <tex>M</tex> {{---}} максимальное паросочетание графа <tex>G</tex>, а <tex>M'</tex> получено из <tex>M</tex> удалением всех рёбер, инцидентных вершинам множества <tex>A</tex>. Тогда <tex>|M'| \geqslant |M| - |A|</tex> и по формуле <tex> \alpha (G - A) = \alpha (G) - |A|</tex> понятно, что <tex>M'</tex> {{---}} максимальное паросочетание графа <tex>G - A</tex>. Более того, из <tex> \alpha (G - A) = \alpha (G) - |A|</tex> следует <tex>|M'| = |M| - |A|</tex>, а значит, все вершины множества <tex>A</tex> покрыты в <tex>M</tex> различными рёбрами. Так как <tex>M'</tex> {{---}} максимальное паросочетание графа <tex>G - A</tex>, то по пунктам <tex>1)</tex> и <tex>2)</tex> очевидно, что <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex> и почти совершенные паросочетания фактор-критических графов <tex>D_1\ldots D_n</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U_1\ldots U_n</tex>.  

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

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

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