4.1 Паросочетания
4.1.1 Не менее важным, чем понятие вершинной независимости (см. тему №5), является понятие рёберной независимости.
Произвольное подмножество попарно несмежных рёбер графа называется паросочетанием (или независимым множеством рёбер). В качестве иллюстрации рассмотрим граф, изображённый на рисунке 4.1. В нём паросочетаниями являются, например, {e2, e6}, {е1, е4, е6}, {e1, e3, e5, e7}.
Паросочетание графа G называется максимальным, если оно не содержится в паросочетании с бóльшим числом рёбер, и наибольшим, если число рёбер в нём наибольшее среди всех паросочетаний графа G. Число рёбер в наибольшем паросочетании графа G называется числом паросочетания и обозначается через α1(G).
Ясно, что независимые множества рёбер графа G находятся во взаимно однозначном соответствии с независимыми множествами вершин рёберного графа L(G), и, следовательно, α1(G)=α0(L(G)). Тем не менее, для нахождения наибóльшего паросочетания в произвольном графе существуют эффективные алгоритмы.
4.1.2 С понятием паросочетания тесно связано понятие рёберного покрытия. Рёберным покрытием графа G называется такое подмножество рёбер Е'ÍEG, которое покрывает все вершины графа, т.е. такое, что каждая вершина в G инцидентна по крайней мере одному ребру из Е'. Из этого определения следует, что лишь графы с изолированными вершинами не имеют рёберных покрытий. Рёберное покрытие графа называется минимальным, если в нём не содержится покрытий с мéньшим числом рёбер, и наименъшим, если число рёбер в нём наименьшее среди всех покрытий. Число рёбер в наименьшем рёберном покрытии графа G называется числом рёберного покрытия и обозначается через β1(G).
Очевидно, что β1(G)≥|G|/2. Например, в графе, изображенном на рисунке 4.2, множество из пяти ребер {{1, 9}, {2, 8}, {3, 7}, {4, 5}, {5, 6}} является рёберным покрытием, а поскольку β1(G)≥4,5, то оно – наименьшее.
4.1.3 Паросочетание называется совершенным (или 1-фактором), если оно одновременно является рёберным покрытием. Иногда сам граф называют паросочетанием – тогда, когда все рёбра графа составляют одно паросочетание.
Так, граф К2 является совершенным паросочетанием (напомним, что граф Кn называется полным, если любые две его вершины из n вершин смежны, т.е. К2 – это граф из двух вершин, соединённых ребром). В графе, изображённом на рисунке 4.1, {е1, ез, e5, е7} – совершенное паросочетание. Очевидно, что если в графе есть совершенное паросочетание, то оно является наименьшим рёберным покрытием.
Кстати, число вершин в наибольшем независимом множестве и число вершин в наименьшем покрытии графа G порядка n связаны соотношением (см. тему 5)
.
Аналогичное верно и для соответствующих рёберных параметров, т.е. справедлива следующая теорема.
Теорема (Т.Галлаи, 1959г.). Для любого графа G порядка n без изолированных вершин верно равенство
.
4.2 Паросочетания в двудольном графе
4.2.1 Самые разные задачи связаны с построением паросочетаний в двудольных графах. Приведём только два примера. Первый из них – задача о свадьбах. Существование решения этой задачи равносильно существованию в специально построенном двудольном графе (X, Y, Е) паросочетания, покрывающего X. В этом графе вершины из X соответствуют юношам, из Y – девушкам, а ребро соединяет вершины, соответствующие знакомым юноше и девушке. На рисунке 4.3 изображён граф для задачи о свадьбах, заданной таблицей 4.1. Жирными линиями выделены рёбра паросочетания, решающего задачу (одно из возможных решений).
Таблица 4.1
| Юноша | Девушки, с которыми знакóм юноша |
| х1 | у1, у4, у5 |
| х2 | у1 |
| х3 | у2, у3, у4 |
| х4 | у2, у4 |
4.2.2 Второй пример – задача о назначениях. Имеется конечное множество исполнителей {х1, x2,..., хn}, каждый из которых может выполнять некоторые из работ {y1, y2,...,yn). Стоимость выполнения работ yi исполнителем xj равна wij. Нужно распределить исполнителей по работам, т.е. назначить по одному исполнителю на каждую работу так, чтобы, во-первых, выполнить все работы и, во-вторых, минимизировать общие затраты. Как и в случае задачи о свадьбах, строится двудольный граф, каждому ребру которого приписывается вес, равный стоимости выполнения исполнителем соответствующей работы. Возможность выполнения всех работ равносильна существованию в графе совершенного паросочетания, а назначение, минимизирующее все затраты, соответствует наибольшему паросочетанию с минимальным суммарным весом.
В следующем подразделе 4.3 мы подробно остановимся на задаче о назначениях и путях её решения.
4.3 Задача о назначениях
4.3.1 Постановка задачи и пути её решения
4.3.1.1 Приведём конкретный пример задачи о назначениях (эту задачу называют также задачей выбора). Пусть n=5 исполнителей с номерами М1, М2,…, М5 способны выполнить пять работ с номерами Т1, Т2,…, Т5. Назначение исполнителя Мi на работу Тj связано с затратами (например, времени) сij. Каждый исполнитель должен быть назначен на одну и только одну работу так, чтобы суммарные затраты на выполнение всех работ были минимальны. Затраты сij приведены в таблице 4.2.
Таблица 4.2
В часах
| Исполнитель | Работа | ||||
| Т1 | Т2 | Т3 | Т4 | Т5 | |
| М1 | |||||
| М2 | |||||
| М3 | |||||
| М4 | |||||
| М5 |
Дадим математическую формулировку задачи. Обозначим через хij число, равное единице, если i -й исполнитель назначен на j -ю работу, и нулю – в противном случае. Тогда задача об оптимальном назначении (назначениях) заключается в отыскании целых неотрицательных чисел хij таких, которые минимизируют целевую функцию
(4.1)
при условиях:
; (4.2)
; (4.3)
. (4.4)
Первое условие (4.2) гарантирует, что за каждой работой будет закреплён исполнитель, причём только один; второе [см. (4.3)] – что каждому исполнителю будет предоставлена работа, причём только одна. Вместо условий целочисленности переменных в последнем ограничении [см. (4.4)] записано условие неотрицательности. В данном случае оно достаточно, так как сформулированная задача является частным случаем задачи линейного программирования транспортного типа, для которой всегда имеется целочисленное решение при целых величинах потребностей и запасов.
Поскольку все суммы по строкам и столбцам равны 1, задача вырождена (напомним, задача называется вырожденной, когда часть базисных переменных равна 0; в транспортной задаче число базисных переменных равно n+n-1, а в нашем случае только n переменных будут равны единице, а n-1 – нулю), так что алгоритм решения транспортной задачи (например, метод потенциалов) применим, но неэффективен. В оптимальном решении (целочисленном) транспортной задачи в нашем случае пять из величин хij будут равны 1, а остальные – 0. С другой стороны, в матрице затрат размерностью 5×5 надо найти пять элементов – по одному в каждой строке и каждом столбце, таких, что сумма выбранных элементов минимальна.
4.3.1.2 Рассмотрим два метода решения задачи о назначениях: венгерский метод и метод Мака. Оба метода основаны на том факте, что положения оптимального выбора (назначения) не меняется, если к каждому элементу некоторой строки или столбца матрицы затрат добавить или вычесть одно и то же значение.
Венгерский метод основан на некоторых довольно запутанных и нетривиальных комбинаторных свойствах матриц и его достаточно трудно, хотя и возможно, программировать. Его описание было приведено в подпункте 3.2.2.3 предыдущей темы. Несмотря на это, мы приведём его и в этой теме.
Метод Мака, предложенный К.Маком, имеет преимущество более простого интуитивного обоснования. Это – логический итеративный процесс. Этот метод основан на идее выбора в каждой строке минимального элемента. Вообще говоря, минимальные элементы строк не распределены по всем n столбцам матрицы. Здесь же используется идея сложения (или вычитания) одного и того же значения со всеми элементами строки или столбца с целью распределения минимальных элементов строк по столбцам (в этом случае они образуют оптимальный выбор).
4.3.2 Венгерский метод решения задачи о назначениях
4.3.2.1 Венгерский метод решения задачи об оптимальных назначениях состоит из начального и общего шагов.
Начальный шаг: выполняем эквивалентное преобразование матрицы С так, чтобы получить матрицу, в которой в каждой строке и каждом столбце имеется хотя бы один ноль; для этого просмотрим каждую строку матрицы С, найдём в ней наименьший элемент и вычтем его из элементов этой строки; полученная при этом матрица С1 называется приведенной по строкам; в матрице С1 просмотрим все столбцы, найдём в каждом из них минимальный элемент и вычтем его из элементов просматриваемого столбца; полученная при этом матрица С2 будет приведенной по строкам и столбцам; клетку, содержащую ноль, будем считать допустимой и с нулями будем обращаться так, как с единицами в упрощённой задаче о назначениях, т.е. при каждом назначении нулевую клетку в строке отмечаем, например «звёздочкой» (знáком «*»); закончив просмотр всех строк, переходим к общему шагу.
Общий шаг состоит из двух шагов:
– шаг 1 – решаем упрощённую задачу о назначениях, т.е расставляем звёздочки среди допустимых клеток; при этом возможны два случая:
а) назначения получают все n исполнителей;
б) назначения получают не все n исполнителей.
В случае а исходная задача о назначениях решена; в случае же б переходим к шагу 2, предварительно сделав пометку строк и столбцов матрицы;
– шаг 2 – зачеркнём каждую непомеченную строку и каждый помеченный столбец; далее рассмотрим часть матрицы, состоящую из незачёркнутых элементов и возьмём наименьшее число в ней (т.е. в этой части матрицы); вычтем это число из всех незачёркнутых элементов и прибавим к дважды зачёркнутым элементам (т.е. к элементам, стоящим на пересечении зачёркнутой строки с зачёркнутым столбцом); далее переходим к шагу 1 общего шага.
Примечание – При переходе к шагу 2 необходимо предварительно пометить строки и столбцы матрицы. Пометим чёрточкой все строки, не содержащие звёздочки. Затем возьмём какую-либо помеченную строку, например i -ую, и просмотрим её, отыскивая допустимые непомеченные клетки (т.е. нулевые без звёздочки клетки). Столбцы, содержащие такие клетки, пометим номером просматриваемой строки, в данном случае номером i. Будем повторять это до тех пор, пока не просмотрим все помеченные (чёрточкой) строки. Столбец, уже получивший какую-нибудь пометку, больше не помечается. Теперьвыберем любой помеченный столбец, например j -й, и просмотрим его, отыскивая звёздочку. Если она (звёздочка) будет найдена, пометим строку, в которой стоит эта звёздочка, номером просматриваемого столбца, в данном случае номером j. Снова выберем какой-либо помеченный непросмотренный столбец и повторим эту операцию. После того как будут просмотрены все помеченные столбцы, переходим к просмотру вновь отмеченных строк, отыскивая в них допустимые невыделенные клетки, и т.д. Продолжаем этот процесс, попеременно просматривая строки и столбцы, пока не достигнем следующего: 1) либо будет помечен столбец, не содержащий звёздочки; 2) либо приписать никаких пометок больше нельзя и все помеченные столбцы содержат звёздочки. В случае 1 общее число звёздочек (назначений) увеличиваем следующим образом. В помеченном столбце, не содержащем звёздочки, поставим звёздочку в клетке, указываемой пометкой этого столбца. Затем в строке, где проставлена новая звёздочка, уберём прежнюю из клетки, указываемой пометкой этой строки. В столбце, в котором находится удаляемая звёздочка, перейдём к клетке, указываемой его пометкой и поставим звёздочку и т.д. В конце концов придём к одной из строк, помеченных чёрточкой, и общее число звёздочек в таблице возрастёт на единицу. После этого сотрём пометки, повторим процесс расстановки пометок и вновь переместим звёздочки, продолжая процесс до тех пор, пока не придём к случаю 2, в котором оптимальное закрепление достигнуто. Минимальное число рядов, содержащих все допустимые клетки, состоит из непомеченных строк и помеченных столбцов.
4.3.2.2 Найдём оптимальное распределение исполнителей по работам при матрице затрат С (см. таблицу 4.2), т.е. решим задачу (4.1)-(4.4) венгерским методом (см. подпункт 4.3.2.1).
После приведения матрицы затрат С по строкам получим матрицу С1 (таблица 4.3). Далее, приведя её по столбцам, получим матрицу С2 (таблица 4.4),
Таблица 4.3 – Матрица С1
| i j | |||||
Таблица 4.4 – Матрица С2
| i j |  1
| |||||
| 0* | ||||||
 3
| 0* | |||||
 0
| 0* | |||||
 6
| 0* | |||||
| – | ||||||
где в каждой строке и в каждом столбце имеется хотя бы один ноль.
Рассматриваем в таблице 4.4 клетки с нулями как допустимые и решаем на них упрощённую задачу о назначениях. Назначения получают четыре исполнителя, а минимальное множество рядов, содержащих все допустимые клетки, составляют непомеченные строки 2, 3, 4 и помеченный столбец 1. Зачеркнув их, находим среди элементов, оставшихся незачёркнутыми в таблице 4.4, наименьший, равный 2. Вычитаем его из всех незачёркнутых элементов таблицы 4.4 и прибавляем ко всем дважды зачёркнутым элементам. Получаем таблицу 4.5, в которой назначения получат уже все исполнители – задача решена.
Таблица 4.5
| i j | |||||
| 0* | |||||
| 0* | |||||
| 0* | |||||
| 0* | |||||
| 0* |
Запишем решение в виде совокупности двойных элементов: (1,5), (2,3), (3,2), (4,4), (5,1), где первый элемент – номер исполнителя Мi, второй – номер поручаемой ему работы Tj. Выбирая из матрицы затрат С (см. таблицу 4.2) соответствующие оптимальным назначениям затраты, получаем минимальные суммарные затраты на выполнение всех работ:
. (4.5)
4.3.3 Метод Мака решения задачи о назначениях
4.3.3.1 Выберем по минимальному элементу в каждой строке. Подчеркнём каждый из этих минимальных элементов. Если в каждом столбце имеется ровно по одному подчёркнутому элементу, то подчёркнутые элементы – базис – определяют оптимальный выбор (назначение). В противном случае переходим к Началу.
Начало. Разделим множество столбцов на два подмножества А и А’, где А – выбранное подмножество, А’ – невыбранное подмножество. В начале (и при последующих возвращениях к Началу) выбранных столбцов нет, так что подмножество А пусто, а подмножество А’ содержит все столбцы. Далее идут следующие шаги;
– шаг 1 – выбрать из подмножества А’ столбец, т.е. один столбец (а не два и более!), содержащий более одного подчёркнутого элемента. Перевести этот столбец из подмножества А’ в подмножество А;
– шаг 2 – пусть подчёркнутый элемент подмножества А из строки i равен bi (рассматриваем строки с подчёркнутыми элементами!), а минимальный элемент множества А’ из строки i равен ai’. Пусть
, (4.6)
где r – номер строки, в которой достигается минимум (4.6);
– шаг 3 – увеличить все элементы множества А на ar’ – br;
– шаг 4 – отметить элемент ar’ точками снизу. Теперь элемент ar’ – «отмеченный точками элемент»;
– шаг 5 – пусть С – столбец, содержащий элемент ar’. Если в С более двух подчёркнутых элементов, то перевести С из множества А’ в множество А и перейти к шагу 2; в противном случае – к следующему шагу. Теперь можно подчеркнуть элементы в ещё одном столбце;
– шаг 6 – подчеркнуть последний элемент ar’ полностью – это новый подчёркнутый элемент;
– шаг 7 – найти исходный подчёркнутый элемент в той же строке, где находится элемент ar’. Удалить подчёркивание. Обозначить столбец, в котором находится этот элемент, через D;
– шаг 8 – Если столбец D не содержит других элементов, он должен содержать элемент, отмеченный точками. Обозначить этот элемент через ar’ и вернуться к шагу 6.
Если столбец D содержит ещё один подчёркнутый элемент, то полностью подчёркнутые элементы образуют новый базис. Если остался ещё столбец без подчёркнутых элементов, то вернуться к Началу.
Если в каждом столбце имеется подчёркнутый элемент, работа алгоритма закончена. Элементы, соответствующие оптимальному выбору, могут быть отмечены в исходной матрице затрат С, и, таким образом, могут быть вычислены соответствующие суммарные минимальные затраты на выполнение всех работ.
Примечание – Вычисления могут быть сокращены, если на шаге 3 алгоритма увеличить на ar’ – br только подчёркнутые элементы множества А, отложив до шага 8 увеличение остальных элементов множества А. В этом случае все оставшиеся элементы столбца увеличиваются на то же значение, на которое увеличились подчёркнутые элементы.
4.3.3.2 Найти оптимальное распределение исполнителей по работам при матрице затрат С (см. таблицу 4.2) методом Мака (см. подпункт 4.3.3.1).
Варианты заданий
Задание №1
Решить задачу о назначениях с матрицей затрат, представленной в таблице 4.6, венгерским методом.
Таблица 4.6
В часах
| Исполнитель | Работа | ||||
| Т1 | Т2 | Т3 | Т4 | Т5 | |
| М1 | |||||
| М2 | |||||
| М3 | |||||
| М4 | |||||
| М5 |