Лекция № 7. Задача о назначениях.

7.1. Определения и основные понятия.

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

Рис. 1.

x₂

v₂

v₁

v₅

x₃

x₁

v₄

v₃

x₄

В графе на рис.1 имеются паросочетания: , , .

Определение 2. Число ребер в паросочетании называется мощностью паросочетания.

В приведенном выше примере .

Определение 3. Паросочетание называется максимальным, если из того, что и – паросочетание, следует, что _.

Замечание 1. В силу конечности графа в нем существует паросочетание максимальной мощности, которое, очевидно, является максимальным. Однако, существуют максимальные паросочетания не максимальной мощности, например, паросочетание в рассмотренном выше примере 1.

Замечание 2. Одной из типичных задач теории графов является задача нахождения паросочетания наибольшей мощности.

Определение 4. Весом или нагрузкой на графе называется неотрицательная функция на множестве ребер графа . Граф с весом будем называть нагруженным графом.

Определение 5. Весом паросочетания в нагруженном графе называется сумма весов всех ребер паросочетания : .

Определение 6. Паросочетание максимального веса назовем максимальным.

Замечание 3. Ранее в определении 3 мы определили паросочетание максимальное в теоретико-множественном смысле. Начиная с этого места максимальным будем называть только паросочетание максимального веса. В силу неотрицательности веса паросочетание максимального веса будет, очевидно, максимальным и в теоретико - множественном смысле.

Далее мы рассматриваем задачу отыскания максимального паросочетания в нагруженном графе : , где - паросочетание в .

Замечание 4. Рассмотренная ранее задача отыскания паросочетания максимальной мощности является частным случаем задачи отыскания максимального паросочетания в нагруженном графе с весом (вес паросочетания в этом случае совпадает с его мощностью).

Определение 6. Граф называется двудольным, если множество его вершин можно разбить на доли и так, что , где - пустое множество, и, если вершины и – смежные, то либо и , либо и .

Двудольный граф будем записывать в виде .

Р ис. 2. Двудольный граф.

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

Р ис. 3. Полный двудольный граф , с .

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

Р ис. 4. Задача о назначениях для

Далее для простоты рассматриваем случай .