Независимые множества в двудольных графах

Описанный метод построения наибольшего паросочетания называют методом чередующихся путей. Он может применяться и для решения других задач. Рассмотрим задачу о независимом множестве. Она трудна в общем случае, но для двудольных графов допускает достаточно быстрое решение с помощью метода чередующихся путей.

Пусть – двудольный граф с долями А и В и требуется найти в нем наибольшее независимое множество. Найдем сначала наибольшее паросочетание М в этом графе. Пусть и соответственно множества свободных вершин в долях А и В. Найдем все вершины из А, достижимые чередующимися путями из , пусть – множество всех таких вершин. Аналогично, пусть – множество все вершин из В, достижимых чередующимися путями из . Обозначим через множество всех вершин из А, не достижимых чередующимися путями ни из , ни из (см. рисунок 10). Вершины из не смежны с вершинами из , так как иначе образовался бы увеличивающий путь. Вершины из тоже не смежны с вершинами из , иначе они были бы достижимы из . Значит, – независимое множество. Оно содержит все свободные вершины и по одной вершине из каждого ребра паросочетания. Отсюда следует, что это независимое множество – наибольшее. Паросочетание М состоит из ребер, а свободных вершин имеется ровно . Следовательно, . Так как , то справедливо следующее утверждение.

Теорема о числе вершинного покрытия двудольного графа. Для любого двудольного графа G выполняется равенство .

Рис. 10.

Задачи

7.1. Найдите наибольшее паросочетание и наименьшее реберное покрытие для графов ,

, .

7.2. Сколько наибольших паросочетаний имеется в графе 1) ; 2) ; 3) ; 4) ;

5) ; 6) ?

7.3. Является ли показанное на рисунке паросочетание наибольшим?

7.4. Сколько имеется максимальных (не имеющих продолжения) чередующихся путей

относительно показанного на рисунке паросочетания, начинающихся в вершине а?

Есть ли среди них увеличивающий путь? Есть ли вообще для данного паросочетания

увеличивающий путь?

7.5. Проверьте, являются ли данные паросочетания наибольшими. Найдите в этих графах

наименьшие реберные покрытия и наибольшие независимые множества.