Материал из Викиконспекты
Паросочетание в двудольном графе
Определение: |
Паросочетание в двудольном графе - произвольное множество ребер двудольного графа, такое что никакие два ребра не имеют общей вершины. Обозначается паросочетание как [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] |
Литература
- Асанов М., Баранский В., Расин В. — Дискретная математика — Графы, матроиды, алгоритмы