Глава 12. ПАРОСОЧЕТАНИЯ, ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ

1. Введение

Рассмотрим следующую задачу построения остовного подграфа общего неориентированного графа степени вершин которого по отношению к подграфу заданы.

Задача об остовном подграфе с предписанными степенями. Пусть неориентированный граф, ребрам которого приписаны веса Пусть, далее, заданы неотрицательные целые числа Требуется найти в такой остовный подграф что степени вершин по отношению к являются заданными числами (т. е. ) и сумма весов ребер графа максимальна (или минимальна).

Сформулированную выше задачу мы будем называть в настоящей главе общей задачей. Очевидно, что если дан граф и числа то вполне возможно, что в не существует никакого остовного подграфа имеющего эти предписанные степени. Два необходимых (но не достаточных, см. разд. 5) условия, которым должны удовлетворять числа чтобы существовал некоторый допустимый остовный подграф, таковы:

и

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

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

ЗМП: найти паросочетание максимального веса. Вес паросочетания определяется как

М будет называться максимальным паросочетанием графа G. ЗМП можно выразить в терминах линейного программирования:

где матрица инциденций графа или в зависимости от того, входит ли ребро в паросочетание.

Совершенно очевидно, что ЗМП для графа является частным случаем общей задачи. Если число вершин четно, то требуется только добавлять к ребра веса до тех пор, пока не получится (новый) полный граф G. ЗМП становится тогда общей задачей для графа где все положены равными 1. Решением ЗМП будет решение общей задачи для (остовного) подграфа если пренебречь теми ребрами в которые имеют вес Если число вершин графа нечетно, то к добавляют одну изолированную вершину, после чего строится граф как это было описано выше.

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

Е будет называться минимальным покрытием графа Формулировка ЗПО в терминах линейного программирования такова:

где или в зависимости от того, входит ли ребро в покрытие.

На рис. 12.1 (а) паросочетание в графе показано жирными линиями, а на рис. 12.1 (б) в том же самом графе жирными линиями показано покрытие.

В частном случае, когда веса всех ребер равны единице, ЗМП и ЗПО сводятся к задаче о наибольшем паросочетании (ЗНПС) и задаче о покрытии наименьшей мощности (ЗПНМ).

Рис. 12.1. (см. скан) (а) Паросочетание. (б) Покрытие.

Если граф имеет вершин, то число ребер в паросочетании графа не может, очевидно, превышать величины Однако это число не всегда достигается; например, для «звездного» графа на рис. 12.2 наибольшее число ребер в паросочетании равно 1.

В том специальном случае, когда веса произвольны, а сам граф является двудольным, задача о максимальном паросочетании

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

В настоящей главе мы дадим эффективные методы решения ЗМП ЗПО, ЗН и ТЗ. ЗМП возникает в качестве подзадачи в задаче об обходе графа и в задаче китайского почтальона.

Рис. 12.2. Звездный граф.

Последние встречаются в задачах распределения, таких, как доставка молока и почты, посыпка зимой дорог смесью соли и песка, сбор мусора (см. гл. 9). ЗН и ТЗ являются двумя основными задачами с многочисленными прямыми и косвенными приложениями в самых различных областях, часто весьма далеких от тех областей, на которые указывают названия этих задач.