Лекции. Теория графов и комбинаторика (стр. 7 )

куб

октаэдр

додекаэдр

икосаэдр

ПАРОСОЧЕТАНИЯ В ДВУДОЛЬНЫХ ГРАФАХ.

Определение 4.

Паросочетанием в любом графе называется подмножество попарно не смежных рёбер.

Определение 5.

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

Определение 6.

Максимальное паросочетание имеет максимальное число рёбер.

Следствие.

– множество всех вершин из Y, смежных с z. Если существует совершенное паросочетание, то

Необходимое и достаточное условие.

Определение 7.

Пусть – двудольный граф, . Произвольно занумеруем рёбра. Возьмём матрицу :

Пример.

Определение 8.

Перманент квадратной матрицы А – сумма модулей всех слагаемых определителей .

Утверждение.

Все совершенные паросочетания в двудольном графе однозначно соответствуют ненулевым слагаемым в .

4Ненулевое слагаемое имеет вид . Покажем, что попарно смежны, т. е. образуют паросочетание. Если и смежны в вершине доли (или доли Y), то слагаемое перманента, содержащее такие рёбра, соответствует выбору одинаковых строк (одинаковых столбцов) матрицы , что невозможно по определению перманента и определителя.3

Теорема 1. (Холла, критического существования совершенного паросочетания)

В двудольном графе существует совершенное паросочетание

4

Уже доказано выше.

Пусть это условие выполняется, но совершенное паросочетание не существует, тогда каждое слагаемое равно 0. Для любой подстановки .

Пусть , тогда строк подматрица из p строк , у которой любой минор порядка p равен 0 (получили противоречие). 3

Пример.

Следствие. (достаточное условие существования совершенного паросочетания)

Пусть .

Если , то совершенное паросочетание существует.

4 Пусть , рассмотрим – множество рёбер, инцидентных вершинам из z.

Пусть

3

Следствие.

Если , то существует совершенное паросочетание.

Лекция № 9.

СПОСОБЫ ПОСТРОЕНИЯ

СОВЕРШЕННОГО ПАРОСОЧЕТАНИЯ.

1.  Условия теоремы Холла (самый не эффективный).

2.  С помощью перманента (универсальный).

Венгерский алгоритм:

Обозначим паросочетания за П («пи»);

Рёбра, входящие в П назовём Т-рёбрами (тёмными);

Остальные рёбра назовём С-рёбрами (светлыми).

1.  Начать с любого П (одно ребро);

2.  Если Т-ребро, инцидентное , то П является совершенным (ВЫХОД), иначе не инцидентная Т-ребру. В этом случае нужно построить дерево цепей, выходящих из вершины и чередующихся по цвету рёбер (С – Т – С…);

3.  Если все цепи закончились Т-рёбрами, то совершенного П не существует (ВЫХОД), иначе существует цепь С – Т – С;

4.  Перекрашиваем все рёбра этой цепи, т. е. ТС, СТ, при этом число Т-рёбер увеличивается на 1;

5.  Взять полученное паросочетание в качестве текущего и вернуться к пункту 2.

Пример.

I способ.

Видно, что найдено совершенное паросочетание, т. к. из каждой вершины X выходит ровно по одному Т-ребру.

II способ.

Задача о назначениях.

Имеется n видов работы и n работников .

– польза от назначения на .

Необходимо распределить работу между работниками так, чтобы получить максимум пользы.

Алгоритм.

Будем приписывать метки и менять их:

– метка вершины ;

– метка вершины .

1. 

2.  Построить двудольный граф, соединив рёбрами ;

3.  Если существует совершенное паросочетание, то оно определяет максимальное назначение (ВЫХОД), иначе построить Венгерским алгоритмом дерево Т цепей, которое доказывает, что совершенного паросочетания нет;

4.  Для каждой вершины вычислить ;

5.  ;