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

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

Паросочетание называется Максимальным, если к нему нельзя добавить ни одного ребра так, чтобы снова получилось паросочетание. Наконец, паросочетание называется Наибольшим, если оно состоит из наибольшего возможного количества ребер. Очевидно, каждое наибольшее паросочетание является максимальным; обратное неверно - вот пример:

Здесь красные ребра - максимальное, но не наибольшее паросочетание, а черные ребра – паро-сочетание наибольшее.

Поиск наибольшего паросочетания в графе представляет собой классческую алгоритми-ческую задачу. Мы рассмотрим ее решение не для общего случая, а для графов частного вида - графов Двудольных. Граф называется Двудольным, если его множество вершин A можно представить в виде объединения двух его непустых подмножеств без общих эле-ментов так, что любое ребро из B будет иметь один конец в , а другой конец - в . Таким образом, нет ни одного ребра, которое соединяло бы вершины из или соединяло бы верши-ны из .

Если считать, что , то двудольный граф можно описать не только известной уже матрицей смежностей, но и следующей Матрицей двудольного графа: эта матрица – размером и, если обозначать ее общий элемент через , то полагают

.

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

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

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

Шаг 0. По матрице данного двудольного графа стро-им рабочую таблицу: она представляет собой матрицу тех же размеров; в клетку с номером поместим символ «´» и назовем ее Недопустимой, если в матрице двудольного графа ; если же , то в клетку рабочей таблицы не запишем ничего и назовем такую клетку До - пустимой. Слева от рабочей таблицы расположим для удобства номера ее строк, а сверху над таблицей расположим номера ее столбцов.

Шаг 1. Просмотрим слева направо первую строку и в первую же допустимую клетку первой строки поставим символ «1». Если в первой строке все клетки недопустимы, то перей-дем ко второй строке и в первую же (при просмотре слева направо) допустимую клетку поста-вим «1». Если же нет допустимых клеток и во второй строке, то проставим указанным выше способом «1» в третьей строке. Если окажется, что во всей таблице все клетки недопустимы, то на этом все действия заканчиваются и выдается ответ: «в графе нет ребер». Если же все-таки удастся поставить первую «1», то после этого просмотрим все остальные строки таблицы в по-рядке возрастания их номеров. В каждой очередной строке просматриваем ее клетки слева на-право и фиксируем первую по ходу просмотра допустимую клетку такую, которая является не-зависимой по отношению к допустимым клеткам, в которых уже стоит символ «1», и простав-ляем в эту клетку «1», после чего переходим к тем же действиям в следующей строке. Если в строке такой клетки не окажется, то переходим к следующей строке и выполняем в ней ту же проверку.

Фиксируем набор ребер в графе, соответствующих проставленным в таблице символам «1». (Под ребром, Соответствующим симво-лу «1» в рабочей таблице, подразумевается следу-ющее: если «1» стоит в клетке с номером , то Соответствующим будет ребро .) Легко заметить, что этот набор ребер - максимальное паросочетание.

Если в результате проведения всех действий на этом шагу в каждой строке рабочей таб-лицы окажется символ «1», то ребра из указанного только что паросочетания и составляют наи-большее паросочетание, и действия окончены. Если же в результате проведения первого шага остались строки без «1», то пометим их справа от таблицы символом «-» переходим к следую-щему шагу.

Шаг 2. Просмотрим все помеченные строки в порядке возрастания их номеров. Про-смотр очередной строки состоит в следующем: в строке отыскиваются допустимые клетки, и столбцы, в которых эти клетки расположены, помечаются номером просматриаемой строки. При этом соблюдается принцип (Ã): Если пометка уже стоит, то на ее место вторая не ставится. Пометки, о которых только что было сказано, физически выставляются внизу, под таблицей.

Если в результате этого шага ни один из столбцов не будет помечен, то это означает, что уже имеющееся паросочетание (полученное на Шаге 1) является искомым наибольшим и все действия прекращаются. Если же среди столбцов появятся помеченные, то переходим к следу-ющему шагу.

Шаг 3. Просмотрим помеченные столбцы в порядке возрастания их номеров. Просмотр столбца состоит в следующем: в столбце отыскивается символ «1» и строка, в которой он распо-ложен, помечается номером просматриваемого столбца.

Физически пометки выставляются справа от таблицы, на уровне соответствующих строк. Всегда соблюдается принцип (Ã).

Если в результате действий по этому шагу возникнет ситуация, когда в просматриваемом столбце нет символа «1», то действия на данном шагу прерываются и надо перейти к следующе-му шагу - Шагу 4. Если же в результате действий по этому шагу будут просмотрены все поме-ченные ранее столбцы и, тем самым, возникнет набор помеченных строк (одни будут помечены символом «-», другие - номерами столбцов), то следует вернуться к Шагу 2 и повторить преду-смотренные им действия.

Если в результате этих действий по Шагу 2 не возникнет новых помеченных столбцов, то это означает, что имеющееся паросочетание является искомым и процесс останавливается. Если же среди помечаемых столбцов возникнут новые помеченные столбцы, то следует повто-рить Шаг 3 с новым набором помеченных столбцов. Если в результате этих действий не возни-кнет новых помеченных строк, то это означает, что имеющееся паросочетание является искомым.

Шаг 4. Рассматривается столбец, имеющий пометку и не содержащий символа «1». Мы сейчас изменим набор символов «1», расположенных в рабочей таблице.

В рассматриваемый столбец поставим символ «1» в строку, номер которой равен помет-ке этого столбца. Затем в этой строке оты-щем «старый» символ «1» и переместим его по его столбцу в строку, номер которой равен пометке при этом столце. (Можно доказать, что опи - санное действие реально всегда осуществимо.) Затем в строке, куда попал последний символ «1» отыщем «старый» символ «1» и с ним проделаем то же самое. В конце концов очередной перемещаемый «старый» символ «1» окажется в строке, где больше символов «1» нет. Возник новый набор символов «1», в котором уже элементов на один больше, чем в исходном наборе символов «1». По этому но-вому набору можно построить паросочетание так же, как это дела-лось в самом начале и после этого повторить все сначала.

В конце концов возникнет одно из указанных выше условий прекращения действий по алгоритму и наибольшее паросочетание ьудет найдено.

Рассмотрим пример. Найти наибольшее паросочетание в следующем двудольном графе со следующей матрицей:

	1	2	3	4	5	6	7	8	9
1	0	1	0	0	0	1	0	1	0
2	1	0	1	1	0	0	0	0	0
3	0	1	0	1	0	0	0	1	0
4	0	1	1	1	1	1	0	1	1
5	0	0	0	1	0	1	0	1	0
6	0	1	0	0	0	1	0	1	0
7	1	0	1	1	0	1	1	0	1
8	0	1	0	1	0	1	0	0	0
9	1	0	0	1	0	0	0	1	0

Сам двудольный граф в этом примере выглядит так:

Будем проводить шаг за шагом описанный выше алгоритм. Рабочая таблица:

	1	2	3	4	5	6	7	8	9
1	´		´	´	´		´		´
2		´			´	´	´	´	´
3	´		´		´	´	´		´
4	´						´
5	´	´	´		´		´		´
6	´		´	´	´		´		´
7		´			´			´
8	´		´		´		´	´	´
9		´	´		´	´	´		´

Выполняем первый шаг: раставляем независимые единицы и отме-чаем строки, в которые единицы не попали:

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´
2	1	´			´	´	´	´	´
3	´		´	1	´	´	´		´
4	´		1				´
5	´	´	´		´	1	´		´
6	´		´	´	´		´	1	´
7		´			´		1	´
8	´		´		´		´	´	´	-
9		´	´		´	´	´		´	-

Паросочетание, которое соответствует выбранным единицам:

.

Далее столбцы допустимых клеток помеченных строк пометим номерами этих строк, следуя принципу (Ã):

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´
2	1	´			´	´	´	´	´
3	´		´	1	´	´	´		´
4	´		1				´
5	´	´	´		´	1	´		´
6	´		´	´	´		´	1	´
7		´			´		1	´
8	´		´		´		´	´	´	-
9		´	´		´	´	´		´	-
	9	8		8		8		9

Далее в помеченных столбцах отыщем единицы и их строки пометим номерами их столбцов:

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´	2
2	1	´			´	´	´	´	´	1
3	´		´	1	´	´	´		´	4
4	´		1				´
5	´	´	´		´	1	´		´	6
6	´		´	´	´		´	1	´	8
7		´			´		1	´
8	´		´		´		´	´	´	-
9		´	´		´	´	´		´	-
	9	8		8		8		9

Теперь снова пометим столбцы, отправляясь от помеченных строк и соблюдая принцип (Ã):

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´	2
2	1	´			´	´	´	´	´	1
3	´		´	1	´	´	´		´	4
4	´		1				´
5	´	´	´		´	1	´		´	6
6	´		´	´	´		´	1	´	8
7		´			´		1	´
8	´		´		´		´	´	´	-
9		´	´		´	´	´		´	-
	9	8	2	8		8		9

Теперь снова просмотрим помеченные столбцы и пометим строки:

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´	2
2	1	´			´	´	´	´	´	1
3	´		´	1	´	´	´		´	4
4	´		1				´			3
5	´	´	´		´	1	´		´	6
6	´		´	´	´		´	1	´	8
7		´			´		1	´
8	´		´		´		´	´	´	-
9		´	´		´	´	´		´	-
	9	8	2	8		8		9

Теперь снова пометим столбцы (при принципе (Ã)):

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´	2
2	1	´			´	´	´	´	´	1
3	´		´	1	´	´	´		´	4
4	´		1				´			3
5	´	´	´		´	1	´		´	6
6	´		´	´	´		´	1	´	8
7		´			´		1	´
8	´		´		´		´	´	´	-
9		´	´		´	´	´		´	-
	9	8	2	8	4	8		9	4

Теперь - снова строки:

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´	2
2	1	´			´	´	´	´	´	1
3	´		´	1	´	´	´		´	4
4	´		1				´			3
5	´	´	´		´	1	´		´	6
6	´		´	´	´		´	1	´	8
7		´			´		1	´		7
8	´		´		´		´	´	´	-
9		´	´		´	´	´		´	-
	9	8	2	8	4	8		9	4

Сложилась ситуация, когда в столбце №9 с пометкой «4» нет едини-цы. Следовательно, можно набор единиц можно увеличить на одну

(старые единицы остаются черными, новые - красные):

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´	2
2	1	´	1		´	´	´	´	´	1
3	´		´	1	´	´	´		´	4
4	´		1				´		1	3
5	´	´	´		´	1	´		´	6
6	´		´	´	´		´	1	´	8
7		´			´		1	´		7
8	´		´		´		´	´	´	-
9	1	´	´		´	´	´		´	-
	9	8	2	8	4	8		9	4

Мы получили новый набор независимых единиц:

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´
2		´	1		´	´	´	´	´
3	´		´	1	´	´	´		´
4	´						´		1
5	´	´	´		´	1	´		´
6	´		´	´	´		´	1	´
7		´			´		1	´
8	´		´		´		´	´	´	-
9	1	´	´		´	´	´		´

Теперь вся процедура повторяется сначала, и на последней таблице уже указана единственная пометка «-» у строки №8. Поме-тим столбцы допустимых клеток этой строки ее номером:

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´
2		´	1		´	´	´	´	´
3	´		´	1	´	´	´		´
4	´						´		1
5	´	´	´		´	1	´		´
6	´		´	´	´		´	1	´
7		´			´		1	´
8	´		´		´		´	´	´	-
9	1	´	´		´	´	´		´
		8		8		8

Затем в помеченных столбцах найдем единицы и их строки пометим

Номерами столбцов:

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´	2
2		´	1		´	´	´	´	´
3	´		´	1	´	´	´		´	4
4	´						´		1
5	´	´	´		´	1	´		´	6
6	´		´	´	´		´	1	´
7		´			´		1	´
8	´		´		´		´	´	´	-
9	1	´	´		´	´	´		´
		8		8		8

Затем столбцы допустимых клеток помеченных строк:

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´	2
2		´	1		´	´	´	´	´
3	´		´	1	´	´	´		´	4
4	´						´		1
5	´	´	´		´	1	´		´	6
6	´		´	´	´		´	1	´
7		´			´		1	´
8	´		´		´		´	´	´	-
9	1	´	´		´	´	´		´
		8		8		8		1

Затем снова строки:

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´	2
2		´	1		´	´	´	´	´
3	´		´	1	´	´	´		´	4
4	´						´		1
5	´	´	´		´	1	´		´	6
6	´		´	´	´		´	1	´	8
7		´			´		1	´
8	´		´		´		´	´	´	-
9	1	´	´		´	´	´		´
		8		8		8		1

Затем снова столбцы:

	1	2	3	4	5	6	7	8	9
1	´	1	´	´	´		´		´	2
2		´	1		´	´	´	´	´
3	´		´	1	´	´	´		´	4
4	´						´		1
5	´	´	´		´	1	´		´	6
6	´		´	´	´		´	1	´	8
7		´			´		1	´
8	´		´		´		´	´	´	-
9	1	´	´		´	´	´		´
		8		8		8		1

Сложилась ситуация, когда расстановка пометок «зациклилась». Это означает, что искомое паросочетание состоит из ребер, соответству-ющих проставленным единицам.

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

Имеется рабочих мест на некотором конвейере и рабочих , кото-рых нужно на эти рабочие места расставить; известа производительность рабочего на рабочем месте . Тот факт, что при некотором распределении на рабочие места рабочий попадает на рабочее место можно описать следующей таблицей:

.

Имея способ S назначения на рабочие места, можно найти конкретную для этого способа минимальную производительность и заметить, что именно эта минимальная производи-тельность и определяет скорость и производительность конвейера. То рабочее место, на кото-ром реализуется минимальная производительность и называют Узким местом в назначении.

Приведем алгоритм решения задачи о назначении на узкие места.

Шаг 0. Фиксируем матрицу производительностей и любое назначенние на рабочие места (например, рабочий назначается на рабочее место ). Пусть - минимальная производительность при этом назначении. Построим рабочую таблицу тех же

Размеров, что и матрица ; в клетку с номером в этой таблице проставим символ «´», если ; в противном случае эту клетку оставим пустой.

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

< Предыдущая		Следующая >