Изменения
Новая страница: «== Паросочетание в двудольном графе== {{Определение |definition= Произвольное множество ребер дв…»
== Паросочетание в двудольном графе==
{{Определение
|definition= Произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины. Обозначается как <tex>M</tex>.}}
{{Определение
|definition= Вершины, принадлежащие <tex>M</tex>, называются покрытыми, не принадлежащие - свободными.}}
{{Определение
|definition= Чередующаяся цепь - путь составленный из ребер двудольного графа, в котором для любых двух соседних ребер выполняется, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
{{Определение
|definition= Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны.}}
{{Теорема
|about=
О максимальном паросочетании и дополняющих цепях
|statement=
Паросочетание <tex>M</tex> в двудольном графе <tex>G</tex> является максимальным тогда и только тогда, когда в <tex>G</tex> нет дополняющей цепи.
|proof=
<tex>\Rightarrow</tex>
Пусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть <tex>M</tex> не являлось максимальным. Противоречие.
<tex>\Leftarrow</tex>
В доказательстве используются несколько новых понятий:
{{Определение
|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> этот путь будет увеличивающим.
}}
{{Определение
|definition= Произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины. Обозначается как <tex>M</tex>.}}
{{Определение
|definition= Вершины, принадлежащие <tex>M</tex>, называются покрытыми, не принадлежащие - свободными.}}
{{Определение
|definition= Чередующаяся цепь - путь составленный из ребер двудольного графа, в котором для любых двух соседних ребер выполняется, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
{{Определение
|definition= Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны.}}
{{Теорема
|about=
О максимальном паросочетании и дополняющих цепях
|statement=
Паросочетание <tex>M</tex> в двудольном графе <tex>G</tex> является максимальным тогда и только тогда, когда в <tex>G</tex> нет дополняющей цепи.
|proof=
<tex>\Rightarrow</tex>
Пусть в двудольном графе <tex>G</tex> с максимальным паросочетанием <tex>M</tex> существует дополняющая цепь. Тогда пройдя по ней и заменив вдоль нее все ребра, входящие в паросочетание, на невходящие и наоборот, мы получим большее паросочетание. То есть <tex>M</tex> не являлось максимальным. Противоречие.
<tex>\Leftarrow</tex>
В доказательстве используются несколько новых понятий:
{{Определение
|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> этот путь будет увеличивающим.
}}
