Лекция 7
Определение паросочений в графе и их разновидностей. Двудольные графы и алгоритм выбора наибольшего паросочетания в двудольном графе. Решение задачи о назначениях на узкие места.
Пусть - граф и - некоторое множество ребер в нем. Множество назы-вается паросочетанием, если любые два ребра из него не имеют общей вершины. Договоримся, что множество из одного ребра тоже будет называться паросочетанием, как и всякое пустое множество.
Паросочетание называется максимальным, если к нему нельзя добавить ни одного ребра так, чтобы снова получилось паросочетание. Наконец, паросочетание называется наибольшим, если оно состоит из наибольшего возможного количества ребер. Очевидно, каждое наибольшее паросочетание является максимальным; обратное неверно - вот пример:
здесь красные ребра - максимальное, но не наибольшее паросочетание, а черные ребра - паро-сочетание наибольшее.
Поиск наибольшего паросочетания в графе представляет собой классческую алгоритми-ческую задачу. Мы рассмотрим ее решение не для общего случая, а для графов частного вида - графов двудольных. Граф называется двудольным, если его множество вершин A можно представить в виде объединения двух его непустых подмножеств без общих эле-ментов так, что любое ребро из B будет иметь один конец в , а другой конец - в . Таким образом, нет ни одного ребра, которое соединяло бы вершины из или соединяло бы верши-ны из .
Если считать, что , то двудольный граф можно описать не только известной уже матрицей смежностей, но и следующей матрицей двудольного графа: эта матрица - размером и, если обозначать ее общий элемент через , то полагают
.
Ясно, что такая матрица описывает граф однозначно, хотя является намного меньшей по объ-ему, чем матрица смежностей графа в этом случае.
Когда множество состоит из вершин, а множество состоит из вершин и в двудольном графе проведены все возможные ребра, то говорят, что двудольный граф является полным двудольным графом и обозначают его символом .
Мы опишем сейчас алгоритм выбора наибольшего сочетания в двудольном графе, опи-раясь на только что введенное понятие матрицы двудольного графа.
Шаг 0. По матрице данного двудольного графа стро-им рабочую таблицу: она представляет собой матрицу тех же размеров; в клетку с номером поместим символ " " и назовем ее недопустимой, если в матрице двудольного графа ; если же , то в клетку рабочей таблицы не запишем ничего и назовем такую клетку до- пустимой. Слева от рабочей таблицы расположим для удобства номера ее строк, а сверху над таблицей расположим номера ее столбцов.
Шаг 1. Просмотрим слева направо первую строку и в первую же допустимую клетку первой строки поставим символ "1". Если в первой строке все клетки недопустимы, то перей-дем ко второй строке и в первую же (при просмотре слева направо) допустимую клетку поста-вим "1". Если же нет допустимых клеток и во второй строке, то проставим указанным выше способом "1" в третьей строке. Если окажется, что во всей таблице все клетки недопустимы, то на этом все действия заканчиваются и выдается ответ: "в графе нет ребер". Если же все-таки удастся поставить первую "1", то после этого просмотрим все остальные строки таблицы в по-рядке возрастания их номеров. В каждой очередной строке просматриваем ее клетки слева на-право и фиксируем первую по ходу просмотра допустимую клетку такую, которая является не-зависимой по отношению к допустимым клеткам, в которых уже стоит символ "1", и простав-ляем в эту клетку "1", после чего переходим к тем же действиям в следующей строке. Если в строке такой клетки не окажется, то переходим к следующей строке и выполняем в ней ту же проверку.
Фиксируем набор ребер в графе, соответствующих проставленным в таблице символам "1". (Под ребром, соответствующим симво-лу "1" в рабочей таблице, подразумевается следу-ющее: если "1" стоит в клетке с номером , то соответствующим будет ребро .) Легко заметить, что этот набор ребер - максимальное паросочетание.
Если в результате проведения всех действий на этом шагу в каждой строке рабочей таб-лицы окажется символ "1", то ребра из указанного только что паросочетания и составляют наи-большее паросочетание, и действия окончены. Если же в результате проведения первого шага остались строки без "1", то пометим их справа от таблицы символом "-" переходим к следую-щему шагу.
Шаг 2. Просмотрим все помеченные строки в порядке возрастания их номеров. Про-смотр очередной строки состоит в следующем: в строке отыскиваются допустимые клетки, и столбцы, в которых эти клетки расположены, помечаются номером просматриаемой строки. При этом соблюдается принцип ( ): если пометка уже стоит, то на ее место вторая не ставится. Пометки, о которых только что было сказано, физически выставляются внизу, под таблицей.
Если в результате этого шага ни один из столбцов не будет помечен, то это означает, что уже имеющееся паросочетание (полученное на Шаге 1) является искомым наибольшим и все действия прекращаются. Если
Читать далее...