А.Н. Подоляка, ст. преподаватель

НАУ «ХАИ», г. Харьков, Украина

О.А. Подоляка, канд. техн. наук

ХНАДУ, г. Харьков, Украина

Е.В. Скакалина, канд. техн. наук

ПНТУ ім. Ю. Кондратюка, г. Полтава, Украина

ЭФФЕКТИВНОЕ РЕШЕНИЕ ЗАДАЧИ ПОКРЫТИЯ ДВУДОЛЬНОГО ГРАФА ЗВЕЗДАМИ И НЕКОТОРЫХ ЕЕ ОБОБЩЕНИЙ

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

Ключевые слова: реберное покрытие графа, звезды, циклы, паросочетания.

У роботі розглядається клас поліноміально вирішуваних задач, які зводяться до задачі покриття дводольних графа зірками, а також деякі схожі складновирішувані задачі, зокрема, комівояжера, тривимірного сполучення і задачі про покриття множин.

Ключові слова: реберне покриття графа, зірки, цикли, паросполучення.

We consider the class of polynomial problems reducible to the problem of the bipartite graph stars covering, as well as some of hard problems: traveling salesman, three-dimensional machining and the set covering problem.

Key words: edge graph covering, stars, cycles, machining.

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

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

-звездным покрытием графа назовем множество ребер графа инцидентных звездам, степень которых не превосходит .

Пусть – весовая функция, тогда вес звездного покрытия определяется как сумма весов его ребер.

(1)

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

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

Выполнение этого условия можно всегда обеспечить путем добавления недостающего количества фиктивных вершин и ребер.

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

(2)

Это функционал задачи поиска наибольшего звездного покрытия в двудольном графе НЗПдг экстремального веса.

Одна из практических интерпретаций задачи может быть следующей. Пусть в организации имеется m автобусов по h посадочных мест в каждом, и задана матрица, определяющая стоимость перевозки пассажира на соответствующем автобусе. Требуется перевезти максимальное число пассажиров по минимальной стоимости (с максимальной для автопредприятия прибылью).

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

Теорема Менгера. Максимальное число реберно-непересекающихся цепей, соединяющих две различные вершины a и b графа, G равно минимальной мощности ab-разделяющего множества (ab-разделяющее множество – это множество ребер, после удаления которых вершины a и b становятся несвязными).

У Форда-Фалкерсона максимальное число реберно-непересекающихся цепей – это разрез, ab-разделяющее множество называется потоком. Эта теорема устанавливает верхнюю границу потока, но ничего не говорит о том, как его искать. Для поиска цепей используют алгоритмы обхода графа.

Чтобы решить задачу ЗН, необходимо уметь находить множества ребер двудольного графа, не имеющих общих концов или паросочетания. Для этого строится сеть невзвешенного двудольного графа. Вершины первой доли связываются с истоком s, а второй со стоком t и затем ищется максимальный поток. Значение найденного потока определяет число ребер наибольшего паросочетания (НП), а ребра двудольного графа, формирующие реберно-непересекающиеся цепи, образуют наибольшее паросочетание.

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

Известны следующие алгоритмы поиска паросочетаний:

1. Куна (чередующиеся цепи) .

2. Микали-Визирани .

3. Матвани-Федера .

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

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

Эффективно решаемые задачи, моделирующие отношения один к одному:

1. Наибольшее паросочетание (НП), чередующиеся цепи (теорема К. Бёрджа). Совершенное паросочетание (теорема Ф. Холла).

2. Задача о назначениях (ЗН) и задача о назначениях на узкое место (Венгерская теорема Д. Кёнига, Э. Эгервари).

3. Трансвенсали, трансвенсальный матроид (теорема Дж. Эдмондса, Д. Фалкерсона, теорема Р. Радо).

4. Цепи и антицепи (теорема Л. Дилворта).

5. Поиск наименьшего вершинного покрытия двудольных графов (теорема Кёнига-Эгервари).

Похожие труднорешаемые задачи:

6. Трехмерное сочетание (3-С).

7. О покрытии множествами (ТП-3).

8. Гамильтонов цикл и циклические перестановки, задача коммивояжёра (ЗК). Вычисление верхней оценки в методе ветвей и границ с помощью решения ЗН.

Новые эффективно решаемые задачи, моделирующие отношения один ко многим:

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

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

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

Новые эффективно решаемые задачи, моделирующие отношения многие ко многим

12. Задача поиска множества наибольших покрытий двудольного графа.

Следует отметить, что задачи 3, 4, 5 эквивалентны задаче поиска паросочетания 1. Формулировки теорем, многие ключевые положения и доказательства собраны в работах [3; 6; 4]. Теорию сложности и классификацию трудных задач можно найти в работах [1; 6; 2].

Трудную задачу 3-С хотелось бы выделить отдельно, т. к. она в некоторой мере похожа на задачу о назначениях и задачу покрытия двудольного графа звездами . Эта задача является одной из шести базовых NP-полных задач по классификации Гери и Джонсона. По аналогии с разрешенными законодательно бракосочетаниями (ЗН), задача 3-С формулируется авторами [1] как задача поиска наибольшего числа законодательно запрещенных бисексуальных групп (сочетаний по три) в трехдольном графе, каждая доля которого соответствует определенному сексуальному типу.

Может показаться, что матрица трехдольного графа напоминает матрицу двудольного и каждая из упомянутых троек представляет собой звезду . И, следовательно, задача 3-С может быть решена как задача НЗПдг. Алгоритм НЗПдг не может эффективно решить данную задачу, поскольку каждая тройка трехмерного сочетания – это цикл. Поэтому 3-С – это задача покрытия трехдольного графа тройными циклами. Кроме того, в НЗПдг следует найти максимальное количество ребер звезд и не требуется, чтобы звезды были максимально полными.

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

Приведенные рассуждения позволяют сформулировать очевидную лемму.

Лемма. Решения задач НП, ТП-3 и 3-С являются подмножествами решений задачи НЗПдг.

Следует отметь, что задачи 9-11, в отличии от задач 1-8, моделируют на порядок более сложное отношение – один ко многим. Данное отношение определяет практические задачи, в которых одному исполнителю назначается несколько работ. Практические постановки указанных задач непосредственно следуют из штатных расписаний, нормативных, технических требований и т. п. Например, один терапевт должен обслуживать n пациентов, одна бригада выполняет n строительных проектов, каждый компьютер кластерной вычислительной системы выполняет заданное число задач.

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

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

В основе алгоритма лежит обобщенная теорема Холла, которая определяет условия существования совершенного звёздного покрытия в невзвешенном двудольном графе. На основании этой теоремы формируется оптимальное множество .

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

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

1. Запрещение. Поиск элемента не принадлежащего оптимальному множествуи его запрещение.

2. Нормализация – уменьшение значения запрещенного элемента , при котором оптимальное множество не изменяется.

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

1. Теоремы запрещений, на основании которых выполняется поиск элемента .

2. Теоремы нормализации.

3. Лемма останова.

Алгоритмизация теорем запрещений сводится к поиску экстремальных элементов мультимножеств, которые в работе названы линейными парами.

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

(1)

Понятно, что выражение (3) определяет путь построения лучшего решения задачи, ключевым звеном этого пути является элемент, называемый линейной парой (ЛП). Элементы формулы (3): и – это линейные пары. Они позволяют сравнивать решения и соответственно выбирать среди них перспективные и отбрасывать однозначно недопустимые.

Пусть – весовая функция ЛП, тогда значением линейной пары строк c и s матрицы будем называть:

, (4)

Элемент будем называть клиентским значением линейной пары, а – серверным значением. Если удобно, индексы клиентской и серверной строк в значении ЛП можно явно не указывать – . Абстрактный тип данных ЛП формируют три обязательных поля: индекс клиентской строки (с), индекс серверной строки(s) и индекс их столбца (j). Эквивалентные обозначения ЛП .

Расстояние между ЛП и определим следующим образом.

(2)

Следует отметить, что в качестве основного критерия, по которому осуществляется сравнение пар, выступает значение ЛП. Поэтому расстояние между ЛП определяет их упорядочение. Однако могут быть и другие дополнительные критерии, в которых учитываются комбинации запрещений клиентских и серверных значений ЛП. Такие пары называются типизированными и в настоящей работе не рассматриваются.

Свойства ЛП:

1. Если к серверному и клиентскому значению ЛП добавить произвольную константу , то значение ЛП не изменится.

2. Если к серверным или клиентским значениям последовательности ЛП добавить произвольную константу , то расстояние между линейными парами последовательности не изменится.

Мультимножество линейных пар (МЛП) – это последовательность линейных пар двух заданных строк. Одна из строк является клиентской, т. к. содержит клиентские значения ЛП, а другая, соответственно, серверной. Нужно понимать, что последовательность пар является мультимножеством (не множеством), т. к. их упорядочение осуществляется на основе значений ЛП, которые могут быть одинаковыми.

Приведенный алгоритм решения НЗП реализует процедуру поиска недопустимых ребер, которая определяет индексы столбцов экстремальных по значению линейных пар в соответствующих МЛП. Следует отметить, что мультимножества имеют ряд особенностей, которые нужно учитывать [7]. Поэтому для МЛП нужно определить понятия экстремального элемента мультимножества, грани и т. п. Приведем эти определения.

Пусть кратность элемента x в множестве есть k_A(x)=k, .

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

1. Все элементы строго больше грани :

, ,.

2. Все элементы больше или равны грани :

,,.

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

Обозначим подмножества индексов столбцов максимальных, наибольших, минимальных и наименьших элементов МЛП некоторой клиентской строки , соответственно: ,,, .

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

Теорема 1. Строгое запрещение ребер. Если в каждом из n различных мультимножеств линейных пар некоторой клиентской строки c существует одно и то же подмножество столбцов мощности , которое определяет клиентские значения наибольших ЛП в каждом из мультимножеств, то все элементы клиентской строки с индексами столбцов не могут формировать оптимальные решения задачи НЗПдг.

Теорема 2. Нестрогое запрещение ребер. Если в каждом из n различных мультимножеств линейных пар некоторой клиентской строки c существует одно и то же подмножество столбцов мощности , которое определяет клиентские значения максимальных ЛП в каждом из мультимножеств, то запрет элементов клиентской строки с индексами столбцов не изменяет вес оптимального решения задачи НЗПдг.

Запрет элемента строки можно трактовать как удаление ребра графа или установку бесконечного веса ребра.

Запрет ребер по теореме 2 может привести к потере некоторых оптимальных решений, но теорема гарантирует, что, по крайней мере, одно оптимальное решение останется.

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

Нормализация запрещенных элементов. Нормализация – процедура эффективного изменения весов запрещенных ребер. Нормализация состоит из двух действий: запрет элемента и изменение его значения на допустимую величину. Следовательно, теоремы запрещения и нормализации тесно связаны. Цель нормализации – рациональное переупорядочение МЛП, при котором возможно запрещение новых недопустимых элементов.

Пусть , мощности множество индексов столбцов наибольших элементов различных МЛП некоторой клиентской строки . Ребра с индексами можно запретить по строгой теореме 1. Отметим, что определяет подмножество наибольших ЛП в каждом из , мультимножеств, и подмножество минимальных элементов .

Пусть грань, тогда ,, ,, .

Расстояние между подмножествами и мультимножества определим следующим образом .

Минимальное расстояние (по всем МЛП)

. (3)

Линейную пару , у которой назовем нормализатором и обозначим.

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

,,, (4)

где – бесконечно малая величина, – множество серверных строк , – ЛП определяющая грань, которая делит МЛП строк и на подмножества и , .

Числа вида , где – основное значение, а – дополнительная часть, назовем близкими. Они реализуются в виде класса с множеством соответствующих операций.

Замечания.

1. Нормализованные ребра считаются допустимыми (в терминах УПК – условно осужденными) для построения решений, в противном случае в доказательствах теорем возможны «сюрпризы».

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

3. Для реализации алгоритма достаточно нестрогой нормализации.

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

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

6. В абстрактном типе данных ЛП бесконечно малая величина может быть представлена логическим значением (ban), которое следует понимать как коэффициент перед .

Остановка алгоритма. Понятно, что после нормализации решения задачи становятся одинаковыми, т. к. становятся равными соответствующие ЛП. Возникает вопрос – когда этот процесс останавливается? Ответ очевиден – этот момент наступит, когда нормализация станет невозможна, т. е. когда она не приводит к уменьшению запрещенных элементов. Это случится, если линейные пары всех МЛП строк или столбцов будут равны. Упомянутая ситуация отражена в лемме останова.

Лемма останова (минимаксная форма). Если в каждом из n-1 различных МЛП матрицы значение минимальной ЛП равно значению максимальной ЛП, то все решения являются равными и оптимальными.

Заключение. Следует отметить, что приведенные в работе теоремы являются обобщением классических теорем Холла и Форда-Фалкерсона для двудольных графов, поэтому представляют собой определенный научный интерес. С их помощью можно эффективно решать известные классические задачи на двудольных графах, моделирующих отношения вида: одна машина – одна работа, а также решать задачи, моделирующие сложные отношения вида: одна машина – много работ.

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

Представленные результаты исследования могут быть использованы при разработке систем календарного планирования и оперативного управления на транспорте, систем управления гибкими автоматизированными системами для предприятий с дискретным характером производства и решения прикладных задач распределения ресурсов [2].

Список использованных источников

1. Гери М. Р. Вычислительные машины и труднорешаемые задачи / М. Р. Гери, Д. С. Джонсон. – М.: Мир, 1982. – 416 с.

2. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М.: МЦНМО, 2000. – 956 с.

3. Ловас Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л. Ловас, М. Пламмер. – М.: Мир, 1998. – 653 с.

4. Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу, К. Стайглиц. – М.: Мир, 1985. – 510 с.

5. Петровский А. Б. Пространства множеств и мультимножеств / А. Б. Петровский. – М.: Едиториал УРСС, 2003. – 248 с.

6. Хопкрофт Д. Введение в теорию автоматов, языков и вычислений / Д. Хопкрофт, Р. Мотвани, Д. Ульман. – 2-е изд. – М.: Вильямс, 2002. – 528 с.

7. Эвнин А. Ю. Вокруг теоремы Холла: учебное пособие / А. Ю. Эвнин. – Челябинск: Изд-во ЮУрГУ, 2004. – 71 с.