6.14. Двудольные графы

• Определение. Граф называется двудольным, если множество его вершин можно разбить на два независимых подмножества таких, что Такой граф будем обозначать как На рис. 6.45 изображен типичный двудольный граф. Двудольные графы играют заметную роль в различных приложениях.

Рис. 6.45

6.14.1. Условия существования двудольных графов

• Теорема 6.14.1. Граф является двудольным тогда и только тогда, когда любой его простой цикл четной длины. Доказательство. Ясно, что данное условие для двудольного графа всегда выполняется. Разобьем граф на компоненты связности Пусть одна из них и а произвольная вершина. Разобьем множество вершин на непересекающиеся где вершины, расстояние до которых от а нечетно; вершины, расстояние до которых от а четно, а Множества являются независимыми. Действительно, если предположить, что вершины и с смежные и

или то существовал бы цикл нечетной длины, соответственно «а нечетная длина b длина единица с нечетная длина a» или «в четная длина длина единица с четная длина a», что противоречит условию. Рассмотренное разбиение вершин выполним для каждой компоненты связности. На рис. 6.46 показано объединение независимых компонент в независимые компоненты и

Рис. 6.46

6.14.2. Паросочетания

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

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

Рис. 6.47

6.14.3. Алгоритм определения максимального паросочетания

Пусть двудольный граф — произвольное паросочетание. Множество вершин (рис. 6.48). Чередующейся цепью относительно паросочетания называется цепь С, в которой ребра поочередно принадлежат которая начинается ребром, не принадлежащим . Заметим, что ребра в цепи не повторяются. Пусть произвольная вершина и ребро, инцидентное вершинам из Построим чередующуюся цепь и допустим, что по такой цепи можно достичь вершины

Рис. 6.48

Такую цепь С можно использовать для получения нового паросочетания , которое содержит на одно ребро больше, чем исходное паросочетание . Действительно, в можно включить все ребра , удалив идобавив Полученное таким образом содержит несмежные ребра, а значит, — паросочетание. Говорят, что получено из чередующимся расширением.

Пример. Дан двудольный граф где . Соединение вершин и задано соотношениями: Найти максимальное паросочетание.

Выберем начальное паросочетание таким образом, что вершину соединяем с вершиной первой незанятой ранее из списка соединений для На рис. 6.49 изображено исходное паросочетание Вершины и 6 не вошли в паросочетание. Попытаемся увеличить , используя алгоритм чередующихся цепей. Обозначим переход по ребрам графа из переход по ребрам паросочетания из в Так, означает, что из можно перейти в вершины 1 и 3, и означает, что из вершин 1 и 3 можно достичь по ребрам паросочетания вершин По алгоритму исходной вершиной цепи является Тогда множество всех чередующихся цепей, начало которых в можно представить: Переходы следует закончить, если вершина 6 достигнута или подмножество вершин доступных из повторилось в чередующейся цепи. В последнем случае вершина 6 не доступна значит, исходное паросочетание максимальное. В нашем случае вершина 6 оказалась доступной. Для выделения исходной чередующейся цепи из всего множества расширяющихся цепей выполним обратный ход: Теперь новое паросочетание строим из старого, исключая из него ребро и включая ребра ( Процесс включения также показан на рис. 6.49. Максимальное паросочетание содержит ребра

Рис. 6.49

• Теорема 6.14.2 о максимальном паросочетании.

Пусть двудольный граф. Тогда количество ребер в максимальном паросочетании равно

где

Доказательство. Пусть — максимальное паросочетание в исходном двудольном графе (рис. 6.50). Паросочетание позволяет рассматривать его как отображение вершин множества в вершины множества по ребрам паросочетания .

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

Аналогично, под будем понимать отображение вершин множества в вершины множества по ребрам U графа. Вершины множеств (рис. 6.50) несмежные, так как паросочетание является максимальным.

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

Для множества А выполняется условие в противном случае множество А можно было бы еще расширить. Следствием расширения множества в процессе его отображения является включение

Обозначим множество Покажем, что найденное множество В удовлетворяет условию теоремы, т. е. Имеем следовательно,

Покажем теперь, что условие теоремы записывается в следующем виде: Тогда ранее найденное множество В, для которого данное неравенство обращается в равенство, будет доказательством условия теоремы. Пусть тогда Отметим, что выполняется неравенство так как вершины множества составляют паросочетание. Тогда верно, что И Теперь количество ребер в максимальном паросочетании можно оценить: Теорема доказана.

6.14.4. Системы различных представителей

Рассмотрим пять множеств: Требуется выбрать такие различные числа что Для данного примера Однако если взять множества то такой выбор оказывается невозможным.

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

6.14.5. Связь системы различных представителей и двудольных графов

Определим двудольный граф соответствующий системе подмножеств. Пусть система подмножеств множества Положим вершинами графа, которые соединены ребрами со своими элементами — смежными им вершинами из (рис. 6.51).

• Лемма 6.14.1. Двудольный граф отвечающий системе подмножеств имеет максимальное паросочетание из ребер тогда и только тогда, когда имеет систему различных представителей. (Доказательство вытекает из определения построения двудольного графа, отвечающего системе различных представителей).

Рис. 6.51

• Теорема 6.14.3 Ф. Холла о существовании системы различных представителей. Система имеет систему различных представителей тогда и только тогда, когда для любой подсистемы выполняется неравенство т.е. количество элементов в объединении любых к подмножеств должно быть не менее k. Доказательство. Необходимое условие теоремы следует из определения системы различных представителей. Каждое подмножество содержит элемент отличный от элементов других подмножеств, а значит

Пусть двудольный граф, соответствующий системе подмножеств Покажем, что в данном графе существует максимальное паросочетание, количество ребер в котором равно Тогда из леммы 6.14.1 будет следовать достаточное условие теоремы. Из теоремы 6.14.2 имеем, что число ребер в максимальном паросочетании равно где . В рамках принятой интерпретации По условию теоремы Таким образом, , а значит, Однако следовательно, (достаточное условие доказано).

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

Существует множество задач, постановки которых укладываются в рамки задачи о назначениях. Рассмотрим две такие постановки.

Задача. Предположим, что вычислительная сеть объединяет специализированных ЭВМ. На вход сети поступают задачи. Известно, что наибольшая производительность конкретной ЭВМ сети достигается на определенном классе задач. Это выражается коэффициентом использования и ЭВМ при решении класса

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

Задача. Группа лиц может выполнить видов работ. Эффективность использования лица на работе определяется мерой ценности Найти оптимальную расстановку людей по видам работ.

• Теорема 6.14.4 — алгоритм поиска оптимальной перестановки .

Пусть матрица целых чисел. Тогда максимум

по всем перестановкам равен минимуму

по всем числам таким, что

Минимум суммы (6.14.2) достигается на перестановке такой, что

Доказательство. Пусть — произвольная перестановка. При изменении от 1 до величины - принимают все значения множества По условию а значит, и для верно Установим связь сумм (6.14.1) и (6.14.2).

Таким образом, сумма (6.14.1) для любой перестановки не больше суммы (6.14.2). Отсюда следует, что теорема будет верна, если мы найдем такие и перестановку , что (6.14.1) и (6.14.2) совпадают.

Шаг 0. Поиск начальных и , удовлетворяющих ограничениям Положим максимальный элемент в строке; условие выполняется. Для матрицы ценностей на рис. 6.52 справа и снизу указаны начальные значения, соответственно

Рис. 6.52. Начальная матрица ценностей

Шаг 1. Фиксируем все и уменьшаем значения до тех пор, пока одно из неравенств не обратится в равенство Эту процедуру выполняем для каждой строки В рассматриваемом примере на рис. 6.53 звездочками отмечены совпадения.

Рис. 6.53. Матрица совпадений

Шаг 2. Для каждого определим множества совпадений

Если обратиться к примеру, то Система множеств может иметь систему различных представителей: все различные. Тогда на перестановке выполняется соотношение а значит, найденная перестановка является оптимальной.

Шаг 3. Предположим, что не имеют системы различных представителей, как в рассматриваемом примере. Тогда нарушается условие теоремы Ф. Холла, т. е. существуют такие, что В нашем примере Перейдем к новым значениям полагая

Остальные и, и остаются без изменений. Обратимся к нашему примеру. На рис. 6.54 показаны новые значения переменных

Рис. 6.54. Новые значения и

Рис. 6.55. Матрица совпадений для новых значений и

При такой замене переменных не нарушается основное условие Действительно, возможны два случая: тогда и а значит, или Отсюда Обозначим тогда новая сумма (6.14.2)

Сумма уменьшилась на к Если теперь перейти к шагу 2, то в случае существования различных представителей для новых значений задача будет решена, в противном случае шаги 2 и 3 алгоритма продолжаем. Так как каждое повторение шагов алгоритма приводит к уменьшению суммы (6.14.2)

следовательно, процесс закончится, что доказывает теорему.

• Замечание. При решении практических задач изменение переменных и, и на 1 может затянуть получение ответа. Заметим, что алгоритм допускает изменение переменных и, и у, на любую величину, не нарушая при этом основного условия:

В рассматриваемом примере сумма уменьшилась на 2, так как Необходимо вернуться на шаг 2. Матрица совпадений примет вид на рис. 6.54, 6.55. Составим для нее систему множеств совпадений Проверим наличие системы различных представителей для данных множеств. Обращаясь к интерпретации системы различных представителей в терминах двудольного графа, надо проверить, что максимальное паросочетание равно для графа где и связь вершин Решая, можно установить, что существуют три таких паросочетания:

Таким образом, существуют три оптимальных назначения:

Ценность назначения составляет