Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа)

4.1 Паросочетания

4.1.1 Более принципиальным, чем понятие вершинной независимости (см. тему №5), является понятие рёберной независимости.

Случайное подмножество попарно несмежных рёбер графа именуется паросочетанием (либо независящим обилием рёбер). В качестве иллюстрации разглядим граф, изображённый на рисунке 4.1. В нём паросочетаниями являются, к примеру, {e2, e6}, {е1, е4, е6}, {e1, e3, e5, e7}.

Паросочетание графа G Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) именуется наибольшим, если оно не содержится в паросочетании с бóльшим числом рёбер, и большим, если число рёбер в нём наибольшее посреди всех паросочетаний графа G. Число рёбер в самом большом паросочетании графа G именуется числом паросочетания и обозначается через α1(G).

Ясно, что независящие огромного количества рёбер графа G Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) находятся во взаимно конкретном согласовании с независящими огромными количествами вершин рёберного графа L(G), и, как следует, α1(G)=α0(L(G)). Все же, для нахождения наибóльшего паросочетания в случайном графе есть действенные методы.

4.1.2 С понятием паросочетания плотно сплетено понятие рёберного покрытия. Рёберным покрытием графа G именуется такое подмножество рёбер Е Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа)'ÍEG, которое покрывает все верхушки графа, т.е. такое, что любая верхушка в G инцидентна по последней мере одному ребру из Е'. Из этого определения следует, что только графы с изолированными верхушками не имеют рёберных покрытий. Рёберное покрытие графа именуется наименьшим, если в нём не содержится покрытий с мéньшим Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) числом рёбер, и наименъшим, если число рёбер в нём меньшее посреди всех покрытий. Число рёбер в меньшем рёберном покрытии графа G именуется числом рёберного покрытия и обозначается через β1(G).

Разумеется, что β1(G)≥|G|/2. К примеру, в графе, изображенном на рисунке 4.2, огромное количество из 5 ребер {{1, 9}, {2, 8}, {3, 7}, {4, 5}, {5, 6}} является рёберным покрытием Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа), а так как β1(G)≥4,5, то оно – меньшее.

4.1.3 Паросочетание именуется совершенным (либо 1-фактором), если оно сразу является рёберным покрытием. Время от времени сам граф именуют паросочетанием – тогда, когда все рёбра графа составляют одно паросочетание.

Так, граф К2 является совершенным паросочетанием (напомним, что граф Кn именуется полным, если любые две Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) его верхушки из n вершин смежны, т.е. К2 – это граф из 2-ух вершин, соединённых ребром). В графе, изображённом на рисунке 4.1, {е1, ез, e5, е7} – совершенное паросочетание. Разумеется, что если в графе есть совершенное паросочетание, то оно является минимальным рёберным покрытием.

Кстати, число вершин в самом большом независящем огромном количестве Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) и число вершин в меньшем покрытии графа G порядка n связаны соотношением (см. тему 5)

.

Аналогичное правильно и для соответственных рёберных характеристик, т.е. справедлива последующая аксиома.

Аксиома (Т.Галлаи, 1959г.). Для хоть какого графа G порядка n без изолированных вершин правильно равенство

.

4.2 Паросочетания в двудольном графе

4.2.1 Самые различные задачки связаны с Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) построением паросочетаний в двудольных графах. Приведём только два примера. 1-ый из их – задачка о свадьбах. Существование решения этой задачки равносильно существованию в специально построенном двудольном графе (X, Y, Е) паросочетания, покрывающего X. В этом графе верхушки из X соответствуют юношам, из Y – девицам, а ребро соединяет верхушки, надлежащие знакомым юноше и Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) девице. На рисунке 4.3 изображён граф для задачки о свадьбах, данной таблицей 4.1. Жирными линиями выделены рёбра паросочетания, решающего задачку (одно из вероятных решений).

Таблица 4.1

Парень Девицы, с которыми знакóм парень
х1 у1, у4, у5
х2 у1
х3 у2, у3, у4
х4 у2, у4

4.2.2 2-ой пример – задачка Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) о назначениях. Имеется конечное огромное количество исполнителей {х1, x2, ..., хn}, любой из которых может делать некие из работ {y1, y2, ...,yn). Цена выполнения работ yi исполнителем xj равна wij. Необходимо распределить исполнителей по работам, т.е. назначить по одному исполнителю на каждую работу так, чтоб, во-1-х, выполнить все Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) работы и, во-2-х, минимизировать общие издержки. Как и в случае задачки о свадьбах, строится двудольный граф, каждому ребру которого приписывается вес, равный цены выполнения исполнителем соответственной работы. Возможность выполнения всех работ равносильна существованию в графе совершенного паросочетания, а предназначение, минимизирующее все издержки, соответствует большему паросочетанию с наименьшим суммарным весом.

В Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) последующем подразделе 4.3 мы тщательно остановимся на задачке о назначениях и путях её решения.

4.3 Задачка о назначениях

4.3.1Постановка задачки и пути её решения

4.3.1.1Приведём определенный пример задачки о назначениях (эту задачку именуют также задачей выбора). Пусть n=5 исполнителей с номерами М1, М2,…, М5 способны выполнить 5 работ с номерами Т1, Т2,…, Т Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа)5. Предназначение исполнителя Мi на работу Тj связано с затратами (к примеру, времени) сij. Каждый исполнитель должен быть назначен на одну и только одну работу так, чтоб суммарные издержки на выполнение всех работ были малы. Издержки сij приведены в таблице 4.2.

Таблица 4.2

В часах

Исполнитель Работа
Т1 Т2 Т3 Т4 Т5
М Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа)1
М2
М3
М4
М5

Дадим математическую формулировку задачки. Обозначим через хij число, равное единице, если i-й исполнитель назначен на j-ю работу, и нулю – в неприятном случае. Тогда задачка об рациональном предназначении (назначениях) заключается в отыскании целых неотрицательных чисел хij таких, которые минимизируют мотивированную функцию

(4.1)

при критериях:

; (4.2)

; (4.3)

. (4.4)

1-ое условие (4.2) гарантирует Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа), что за каждой работой будет закреплён исполнитель, причём только один; 2-ое [см. (4.3)] – что каждому исполнителю будет предоставлена работа, причём только одна. Заместо критерий целочисленности переменных в последнем ограничении [см. (4.4)] записано условие неотрицательности. В этом случае оно довольно, потому что сформулированная задачка является личным случаем задачки линейного программирования транспортного Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) типа, для которой всегда имеется целочисленное решение при целых величинах потребностей и припасов.

Так как все суммы по строчкам и столбцам равны 1, задачка вырождена (напомним, задачка именуется вырожденной, когда часть базовых переменных равна 0; в транспортной задачке число базовых переменных равно n+n-1, а в нашем случае только n переменных будут равны Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) единице, а n-1 – нулю), так что метод решения транспортной задачки (к примеру, способ потенциалов) применим, но неэффективен. В рациональном решении (целочисленном) транспортной задачки в нашем случае 5 из величин хij будут равны 1, а другие – 0. С другой стороны, в матрице издержек размерностью 5×5 нужно отыскать 5 частей – по одному в каждой строке и Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) каждом столбце, таких, что сумма избранных частей мала.

4.3.1.2Разглядим два способа решения задачки о назначениях: венгерский способ и способ Мака. Оба способа основаны на том факте, что положения рационального выбора (предназначения) не изменяется, если к каждому элементу некой строчки либо столбца матрицы издержек добавить либо отнять одно и Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) то же значение.

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

Способ Мака, предложенный К.Маком Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа), имеет преимущество более обычного интуитивного обоснования. Это – логический итеративный процесс. Этот способ основан на идее выбора в каждой строке малого элемента. Вообщем говоря, малые элементы строк не распределены по всем n столбцам матрицы. Тут же употребляется мысль сложения (либо вычитания) 1-го и такого же значения со всеми элементами строчки либо столбца Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) с целью рассредотачивания малых частей строк по столбцам (в данном случае они образуют лучший выбор).

4.3.2Венгерский способ решения задачки о назначениях

4.3.2.1Венгерский способ решения задачки об хороших назначениях состоит из исходного и общего шагов.

Исходный шаг: исполняем эквивалентное преобразование матрицы С так, чтоб получить матрицу, в какой в каждой Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) строке и каждом столбце имеется хотя бы один ноль; для этого просмотрим каждую строчку матрицы С, найдём в ней меньший элемент и вычтем его из частей этой строчки; приобретенная при всем этом матрица С1 именуется приведенной по строчкам; в матрице С1 просмотрим все столбцы, найдём в каждом из Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) их малый элемент и вычтем его из частей просматриваемого столбца; приобретенная при всем этом матрица С2 будет приведенной по строчкам и столбцам; клеточку, содержащую ноль, будем считать допустимой и с нулями будем обращаться так, как с единицами в упрощённой задачке о назначениях, т.е. при каждом предназначении нулевую клеточку в строке Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) отмечаем, к примеру «звёздочкой» (знáком «*»); окончив просмотр всех строк, перебегаем к общему шагу.

Общий шаг состоит из 2-ух шагов:

– шаг 1 – решаем упрощённую задачку о назначениях, т.е расставляем звёздочки посреди допустимых клеток; при всем этом вероятны два варианта:

а) предназначения получают все n исполнителей;

б) предназначения получают Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) не все n исполнителей.

В случае а начальная задачка о назначениях решена; в случае же б перебегаем к шагу 2, за ранее сделав пометку строк и столбцов матрицы;

– шаг 2 – зачеркнём каждую непомеченную строчку и каждый помеченный столбец; дальше разглядим часть матрицы, состоящую из незачёркнутых частей и возьмём меньшее число в ней (т Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа).е. в этой части матрицы); вычтем это число из всех незачёркнутых частей и прибавим к два раза зачёркнутым элементам (т.е. к элементам, стоящим на скрещении зачёркнутой строчки с зачёркнутым столбцом); дальше перебегаем к шагу 1 общего шага.

Примечание – При переходе к шагу 2 нужно за ранее пометить строчки и Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) столбцы матрицы. Пометим чёрточкой все строчки, не содержащие звёздочки. Потом возьмём какую-либо помеченную строчку, к примеру i-ую, и просмотрим её, отыскивая допустимые непомеченные клеточки (т.е. нулевые без звёздочки клеточки). Столбцы, содержащие такие клеточки, пометим номером просматриваемой строчки, в этом случае номером i. Будем повторять Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) это до того времени, пока не просмотрим все помеченные (чёрточкой) строчки. Столбец, уже получивший какую-нибудь пометку, больше не помечается. Теперьвыберем хоть какой помеченный столбец, к примеру j-й, и просмотрим его, отыскивая звёздочку. Если она (звёздочка) будет найдена, пометим строчку, в какой стоит эта звёздочка, номером просматриваемого столбца, в Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) этом случае номером j. Опять выберем какой-нибудь помеченный непросмотренный столбец и повторим эту операцию. После того как будут просмотрены все помеченные столбцы, перебегаем к просмотру вновь отмеченных строк, отыскивая в их допустимые невыделенные клеточки, и т.д. Продолжаем этот процесс, попеременно просматривая строчки и столбцы, пока не достигнем Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) последующего: 1) или будет помечен столбец, не содержащий звёздочки; 2) или приписать никаких пометок больше нельзя и все помеченные столбцы содержат звёздочки. В случае 1 общее число звёздочек (предназначений) увеличиваем последующим образом. В помеченном столбце, не содержащем звёздочки, поставим звёздочку в клеточке, указываемой пометкой этого столбца. Потом в строке, где проставлена новенькая звёздочка, уберём Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) прежнюю из клеточки, указываемой пометкой этой строчки. В столбце, в каком находится удаляемая звёздочка, перейдём к клеточке, указываемой его пометкой и поставим звёздочку и т.д. В конце концов придём к одной из строк, помеченных чёрточкой, и общее число звёздочек в таблице возрастёт на единицу. После чего сотрём пометки Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа), повторим процесс расстановки пометок и вновь переместим звёздочки, продолжая процесс до того времени, пока не придём к случаю 2, в каком наилучшее закрепление достигнуто. Малое число рядов, содержащих все допустимые клеточки, состоит из непомеченных строк и помеченных столбцов.

4.3.2.2Найдём наилучшее рассредотачивание исполнителей по работам при матрице издержек С Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) (см. таблицу 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: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) хотя бы один ноль.

Рассматриваем в таблице 4.4 клеточки с нулями как допустимые и решаем на их упрощённую задачку о назначениях. Предназначения получают четыре исполнителя, а малое огромное количество рядов, содержащих все допустимые клеточки, составляют непомеченные строчки 2, 3, 4 и помеченный столбец 1. Зачеркнув их, находим посреди частей, оставшихся незачёркнутыми в таблице Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) 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), где 1-ый элемент – номер исполнителя Мi, 2-ой – номер поручаемой ему работы Tj Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа). Выбирая из матрицы издержек С (см. таблицу 4.2) надлежащие хорошим назначениям издержки, получаем малые суммарные издержки на выполнение всех работ:

. (4.5)

4.3.3Способ Мака решения задачки о назначениях

4.3.3.1Выберем по наименьшему элементу в каждой строке. Подчеркнём любой из этих малых частей. Если в каждом столбце имеется ровно по одному подчёркнутому элементу, то подчёркнутые Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) элементы – базис – определяют лучший выбор (предназначение). В неприятном случае перебегаем к Началу.

Начало. Разделим огромное количество столбцов на два подмножества А и А’, где А – выбранное подмножество, А’ – невыбранное подмножество. Сначала (и при следующих возвращениях к Началу) избранных столбцов нет, так что подмножество А пусто, а подмножество А Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа)’ содержит все столбцы. Дальше идут последующие шаги;

– шаг 1 – избрать из подмножества А’ столбец, т.е. один столбец (а не два и поболее!), содержащий более 1-го подчёркнутого элемента. Перевести этот столбец из подмножества А’ в подмножество А;

– шаг 2 – пусть подчёркнутый элемент подмножества А из строчки i равен bi (рассматриваем строчки с Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) подчёркнутыми элементами!), а малый элемент огромного количества А’ из строчки i равен ai’. Пусть

, (4.6)

где r – номер строчки, в какой достигается минимум (4.6);

– шаг 3 – прирастить все элементы огромного количества А на ar’– br;

– шаг 4 – отметить элемент ar’ точками снизу. Сейчас элемент ar’ – «отмеченный точками элемент»;

– шаг 5 – пусть С – столбец, содержащий Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) элемент ar’. Если в С более 2-ух подчёркнутых частей, то перевести С из огромного количества А’ в огромное количество А и перейти к шагу 2; в неприятном случае – к последующему шагу. Сейчас можно выделить элементы в ещё одном столбце;

– шаг 6 – выделить последний элемент ar’ вполне – это новый подчёркнутый элемент;

– шаг 7 – отыскать Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) начальный подчёркнутый элемент в той же строке, где находится элемент ar’. Удалить подчёркивание. Обозначить столбец, в каком находится этот элемент, через D;

– шаг 8 – Если столбец D не содержит других частей, он должен содержать элемент, отмеченный точками. Обозначить этот элемент через ar’ и возвратиться к шагу 6.

Если столбец D содержит ещё один Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) подчёркнутый элемент, то на сто процентов подчёркнутые элементы образуют новый базис. Если остался ещё столбец без подчёркнутых частей, то возвратиться к Началу.

Если в каждом столбце имеется подчёркнутый элемент, работа метода закончена. Элементы, надлежащие хорошему выбору, могут быть отмечены в начальной матрице издержек С, и, таким Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) макаром, могут быть вычислены надлежащие суммарные малые издержки на выполнение всех работ.

Примечание – Вычисления могут быть сокращены, если на шаге 3 метода прирастить на ar’– br только подчёркнутые элементы огромного количества А, отложив до шага 8 повышение других частей огромного количества А. В данном случае все оставшиеся элементы столбца растут на то Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа) же значение, на которое возросли подчёркнутые элементы.

4.3.3.2Отыскать среднее рассредотачивание исполнителей по работам при матрице издержек С (см. таблицу 4.2) способом Мака (см. подпункт 4.3.3.1).

Варианты заданий

Задание №1

Решить задачку о назначениях с матрицей издержек, представленной в таблице 4.6, венгерским способом.

Таблица 4.6

В часах

Исполнитель Работа
Т1 Т2 Т3 Т4 Т5
М1
М2
М Тема №4: «Паросочетания в двудольном графе. Задача о назначениях» (3 часа)3
М4
М5


tema-4-proishozhdenie-i-razvitie-chelovecheskogo-soznaniya.html
tema-4-proizvodstvo-zagotovok-iz-poroshkovih-materialov.html
tema-4-psihofiziologicheskie-osnovi-uchebnogo-truda-i-intellektualnoj-deyatelnosti-sredstva-fizicheskoj-kulturi-v-regulirovanii-rabotosposobnosti.html