Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Паросочетание в двудольном графе== {{Определение |definition= Произвольное множество ребер дв…»)
 
Строка 23: Строка 23:
 
В доказательстве используются несколько новых понятий:
 
В доказательстве используются несколько новых понятий:
 
{{Определение
 
{{Определение
|definition= Увеличивающая цепь - }}
+
|definition= Увеличивающая цепь - чередующаяся цепь, у которой оба конца свободны.}}
 
{{Определение
 
{{Определение
|definition= Уменьшающая цепь - }}
+
|definition= Уменьшающая цепь - чередующаяся цепь, у которой оба конца покрыты.}}
 
{{Определение
 
{{Определение
|definition= Сбалансированная цепь - }}
+
|definition= Сбалансированная цепь - чередующаяся цепь, у которой один конец свободен, а другой покрыт}}
Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> - не наибольшее. Докажем, что тогда имеется увеличивающий путь относительно <tex>M</tex>. Пусть <tex>M'</tex> - другое паросочетание и <tex>|M'|>|M|</tex>. Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, образованный теми ребрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством ребер графа <tex>H</tex> является симметрическая разность <tex>M\otimes M'</tex>. В графе <tex>H</tex> каждая вершина инцидентна не более чем двум ребрам (одному из <tex>M</tex> и одному из <tex>M'</tex> ), т.е. имеет степень не более двух. В таком графе каждая компонента связности - путь или цикл. В каждом из этих путей и циклов чередуются ребра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>, имеется компонента, в которой ребер из <tex>M'</tex> содержится больше, чем ребер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь будет увеличивающим.
+
 
 +
Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> - не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>. Пусть <tex>M'</tex> - другое паросочетание и <tex>|M'|>|M|</tex>. Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, образованный теми ребрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством ребер графа <tex>H</tex> является симметрическая разность <tex>M\otimes M'</tex>. В графе <tex>H</tex> каждая вершина инцидентна не более чем двум ребрам (одному из <tex>M</tex> и одному из <tex>M'</tex> ), т.е. имеет степень не более двух. В таком графе каждая компонента связности - путь или цикл. В каждом из этих путей и циклов чередуются ребра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>, имеется компонента, в которой ребер из <tex>M'</tex> содержится больше, чем ребер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь является увеличивающей цепью.
 
}}
 
}}

Версия 21:59, 11 декабря 2010

Паросочетание в двудольном графе

Определение:
Произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины. Обозначается как [math]M[/math].


Определение:
Вершины, принадлежащие [math]M[/math], называются покрытыми, не принадлежащие - свободными.


Определение:
Чередующаяся цепь - путь составленный из ребер двудольного графа, в котором для любых двух соседних ребер выполняется, что одно из них принадлежит паросочетанию [math]M[/math], а другое нет.


Определение:
Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны.
Теорема (О максимальном паросочетании и дополняющих цепях):
Паросочетание [math]M[/math] в двудольном графе [math]G[/math] является максимальным тогда и только тогда, когда в [math]G[/math] нет дополняющей цепи.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

Пусть в двудольном графе [math]G[/math] с максимальным паросочетанием [math]M[/math] существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть [math]M[/math] не являлось максимальным. Противоречие.

[math]\Leftarrow[/math]

В доказательстве используются несколько новых понятий:

Определение:
Увеличивающая цепь - чередующаяся цепь, у которой оба конца свободны.


Определение:
Уменьшающая цепь - чередующаяся цепь, у которой оба конца покрыты.


Определение:
Сбалансированная цепь - чередующаяся цепь, у которой один конец свободен, а другой покрыт


Рассмотрим паросочетание [math]M[/math] в графе [math]G[/math] и предположим, что [math]M[/math] - не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно [math]M[/math]. Пусть [math]M'[/math] - другое паросочетание и [math]|M'|\gt |M|[/math]. Рассмотрим подграф [math]H[/math] графа [math]G[/math], образованный теми ребрами, которые входят в одно и только в одно из паросочетаний [math]M[/math], [math]M'[/math]. Иначе говоря, множеством ребер графа [math]H[/math] является симметрическая разность [math]M\otimes M'[/math]. В графе [math]H[/math] каждая вершина инцидентна не более чем двум ребрам (одному из [math]M[/math] и одному из [math]M'[/math] ), т.е. имеет степень не более двух. В таком графе каждая компонента связности - путь или цикл. В каждом из этих путей и циклов чередуются ребра из [math]M[/math] и [math]M'[/math]. Так как [math]|M'|\gt |M|[/math], имеется компонента, в которой ребер из [math]M'[/math] содержится больше, чем ребер из [math]M[/math]. Это может быть только путь, у которого оба концевых ребра принадлежат [math]M'[/math]. Заметим, что относительно [math]M[/math] этот путь является увеличивающей цепью.
[math]\triangleleft[/math]