Задача назначения

Естественным обобщением рассмотренной в разделе 1 задачи поиска максимального па-росочетания является задача поиска максимального взвешенного паросочетания. Суть дела в том, что каждому ребру заданного двудольного графа сопоставлено некоторая положительное число – вес ребра. Рассматриваемая задача состоит в поиске паросочетания с максимальным суммарным весом. Легко понять, что рассмотренная в разделе 1 задача является частным случа-ем последней задачи, когда веса всех рёбер равны 1.

Во многих случаях вершины 1-ой доли интерпретируются как исполнители, вершины 2-ой доли – как работы, а наличие соединяющего их ребра с весом a – как возможность выполнения данной работы данным исполнителем с эффективностью (доходом) a. При такой интерпретации задача поиска максимального взвешенного паросочетания представляет собой поиск такого рас-пределения задач по исполнителям, при котором суммарная эффективность будет максималь-ной. Именно поэтому рассматриваемая задача чаще называется задачей назначения (работ ис-полнителям). Настоящий раздел и посвящён этой задаче.

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

Пусть G (V, E)– двудольный граф, V = X Y, где X и Y – множества вершин первой и вто-рой доли графа G, С – произвольный цикл в графе G. Нетрудно понять, что число рёбер в лю-бом цикле двудольного графа чётно. Обозначим через С ₁ множество рёбер цикла, взятых через одно, а через С ₂ – множество остальных рёбер этого цикла (также взятых через одно). Пусть P – произвольное паросочетание в графе G. Определим множество рёбер P’ следующим образом:

P’ = (P С ₁) С ₂. (1)

Имеет место

Утверждение 1. Для любого паросочетания P и любого цикла C множество P’ также явля-ется паросочетанием.

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

Каждому ребру (v, w) графа G сопоставлен неотрицательный вес с (v, w) ≥ 0. Задачей о максимальном взвешенном паросочетании в двудольном графе G называется задача нахожде-ния в нём паросочетания, суммарный вес рёбер которого максимален.

Алгоритм решения этой задачи, как и большинства других задач оптимизации на графах, состоит в последовательном переходе от одних паросочетаний к другим, с бóльшим суммарным весом (т.е. к лучшим с рассматриваемой точки зрения), до тех пор, пока не будет достигнуто решение. Ниже будет описан один этап алгоритма – переход от произвольного паросочетания к следующему.

Алгоритм 1 улучшения заданного паросочетания. Исходное паросочетание P состоит из рёбер (x ₁, y ₁), (x ₂, y ₂), …, (x_n, y_n).

1. По заданному двудольному графу G и паросочетанию P построим ориентированный взвешенный граф G * следующим образом:

· множество вершин графа G * совпадает с множеством вершин графа G;

· каждое ребро (x_k, y_k) Î P определяет дугу (x_k, y_k) графа G * с тем же весом с (x_k, y_k), каким обладает ребро (x_k, y_k) в исходном графе;

· каждое ребро (x_k, y_k) Ï P определяет дугу (y_k, x_k) графа G * с весом − с (x_k, y_k).

2. С помощью алгоритма Флойда-Уоршолла находим в графе G * орцикл отрицательной стоимости (если таковой существует). Отсутствие орциклов в графе G * означает, что исходное взвешенное паросочетание P максимально. Алгоритм улучшения прекращает работу.

3. Разобьём множество дуг найденного орцикла С на два подмножества С ₁ и С ₂, где все дуги, принадлежащие С ₁, ведут из X в Y, а все дуги, принадлежащие С ₂, ведут из Y в X. Более того, если перейти от дуг (отменой ориентации) обратно к рёбрам G, то, по построению, все рёбра из С ₁ содержатся в исходном паросочетании P, а все рёбра из С ₂ не содержатся в нём. Также по построению, веса всех дуг из С ₁ совпадают с исходными весами дуг в графе G, а веса всех дуг из С ₂ равны исходным весам со знаком −. Поскольку сумма весов во всех дугах цикла отрицательна, то это означает, что в исходном графе сумма весов у всех дуг, входящих в мно-жество С ₂, строго больше, чем сумма весов во всех дугах, входящих в множество С ₁.

4. Рассмотрим цикл С в исходном графе G, и два его подмножества чередующихся рёбер С ₁ и С ₂, которые были определены на шаге 3. Определим по исходному паросочетанию P и множествам рёбер С ₁ и С ₂ новое паросочетание P’ формулой (1):

P’ = (P С ₁) С ₂.

На шаге 3 было отмечено, что все рёбра из С ₁ входят в P, а все рёбра из С ₂ не входят в P. Так как суммарный вес всех дуг, входящих в С ₂, по построению строго больше, чем суммарный вес всех дуг, входящих в С ₁, то ровно настолько же вес нового паросочетания P’ больше, чем вес исходного паросочетания P. Таким образом, новое паросочетание имеет бóльший вес, чем ис-ходное ■

Алгоритм построения максимального взвешенного паросочетания сводится к двум шагам. На 1-ом шаге строится начальное паросочетание (например, потоковым алгоритмом из раздела 1). 2-ой шаг состоит в многократном применении только что описанного алгоритма 1 – до тех пор, пока на шаге 2 этого алгоритма будет установлено отсутствие циклов отрицательной длины.

Пример 2. Проиллюстрируем алгоритм построения максимального взвешенного паросо-четания. Исходный взвешенный двудольный граф G показан на рис.4.1. Веса рёбер указаны ря-

Рис.4.1 Рис.4.2

ом с ними; номера вершин указаны в кружках. Рёбра начального паросочетания P = {(1,4), (2,5), (3,6)} на рис.4.1 выделены. Вес выделенного паросочетания равен 7.

На рис.4.2 показан построенный по исходному паросочетанию P орграф G *. В соответст-вии с алгоритмом 1 все рёбра исходного паросочетания превращаются в дуги с положительными

весами, ориентированные от доли X к доле Y, а все остальные рёбра превращаются в дуги с отрицательными весами, ориентированные от доли Y к доле X. В графе G * существует орцикл 1→4 →3→6→1 с отрицательным весом 2 – 4 + 3 – 10 = – 9. В этом цикле С ₁ = {(1,4), (3,6)}, С ₂ = {(6,1), (4,3)}. Возвращаясь к исходному графу и отменяя ориентации, получаем С ₂ = {(1,6), (3, 4)}.

Далее, в соответствии с формулой (1), получим новое паросочетание P’ = (P С ₁) С ₂ = ({(1,4), (2,5), (3,6)} {(1,4), (3,6)}) {(1,6), (3,4)} = {(2,5), (1,6), (3,4)} (см. определения и алгоритмы выполнения теоретико-множественных операций в разделе 2-3). Это новое паросо-четание выделено на рис.4.3. Строя по нему орраф G *, как указано на шаге 1 алгоритма 1, при-ходим к орграфу, показанному на рис.4.4.

Рис.4.3 Рис.4.4

Можно непосредственно убедиться (не прибегая к помощи алгоритма Флойд-Уоршолла), что в последнем орграфе орциклы отрицательной длины отсутствуют. Поэтому последнее паро-сочетание, показанное на рис.4.3, будет максимальным. Его вес равен 16. Оно превосходит вес (7) предыдущего паросочетания на 9 – в соответствии с теорией, как раз настолько, насколько сумма весов рёбер из множества С ₂ = {(1,6), (3,4)}, равная 14, больше суммы весов рёбер из множества С ₁ = {(1,4), (3,6)}, равной 5 ■

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

01 02

03 04

05 06

07 08

09 10

11 12

13 14

15 16

■

Дата добавления: 2015-10-16