Задачи на графах

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

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

Своим названием задача о наименьшем покрытии обязана теоретико-множественной трактовке. Она состоит в следующем. Дано конечное множество Я и семейство 0 = {5,, 52, ..., <5^}, 5, с Я. Любое подсемейство 0' = {5. ,5. , ..., } семейства 0

такое, что 0 = Я называется покрытием множества Я, а множе-

/=1

ства называются покрывающими множествами. Если покрывающие множества попарно не пересекаются, то (2' — это разбиение множества на классы.

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

к

этом стоимость подсемейства 0' определяется как ^сУ/.

/=1

Предположим, что организации необходимо нанять переводчиков с французского, немецкого, греческого, итальянского, испанского, русского и китайского языков на английский язык и что имеется пять кандидатур А, В, С, Д Е переводчиков. Каждый переводчик владеет только некоторым набором языков, с которых он может переводить на английский, и требует вполне определенную зарплату. Необходимо решить, каких переводчиков необходимо взять на работу, чтобы минимизировать затраты на зарплату. Это задача о наименьшем покрытии. Перечень языков, с которых необходим перевод на английский — это множество Я. Кандидаты из семейства А, В, С, Д Е— покрывающие подмножества 5) С соответствующей СТОИМОСТЬЮ Су .

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

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

Язык

А

Я*

с'

?>*

Е

Французский

1

0

1

1

0

Немецкий

1

1

0

0

0

Греческий

0

1

0

0

0

Итальянский

1

0

0

1

0

Испанский

0

0

1

0

0

Русский

0

1

1

0

1

Китайский

0

0

0

1

1

Стоимость каждого маршрута доставки груза и возврата j равна с}. Необходимо определить, сколько машин требуется для доставки груза в один день, чтобы расходы были минимальные. В данном случае исходное множество Я — это потребители, покрывающие подмножество 0' — машины.

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

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

Задача о раскраске графа изучалась очень давно, примерно с середины XIX века. Доказано, что если граф планарный, то его можно раскрасить, используя пять цветов. Гипотеза о том, что планарный граф может быть раскрашен при помощи четырех цветов, обоснована с привлечением ЭВМ.

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

Рассмотрим следующую задачу. Для выполнения п работ требуется т ресурсов. Каждая работа выполняется за одинаковое время и требует для этого некоторые объемы ресурсов. Другая работа может потребовать одни и те же их типы, часть одних и тех же типов или совершенно другие ресурсы. Сокращение общего времени выполнения работ происходит тогда, когда большинство из них выполняется параллельно. Требуется распределить ресурсы так, чтобы минимизировать общее время выполнения всех работ.

Сформулируем задачу в терминах графов. Каждой работе поставим в соответствие вершину графа С. Вершины графа хп х] соединим ребром тогда и только тогда, когда для выполнения /'-й и у работ требуется один и тот же ресурс. Это означает, что эти работы не могут выполняться одновременно. Тогда раскраска графа С определит некоторое распределение ресурсов по работам такое, что работы, соответствующие вершинам одного цвета, могут выполниться параллельно. Поиск наименьшего значения хроматического числа г даст оптимальное решение задачи.

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

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

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

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

В других задачах размещения, таких, например, как выбор места размещения склада в сети дорог, трансформаторных подстанций, АТС и др., требуется так расположить пункт обслуживания, чтобы сумма кратчайших расстояний от этого пункта до объектов обслуживания, представляемых вершинами графов, была минимальной. Такие задачи называют минисуммными задачами размещения, а найденные в результате их решения места размещения центров обслуживания — медианами графов.

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

Важное практическое значение имеют задачи на графах, связанные с выделением в графе его остовного дерева. Таким деревом или просто остовом в неориентированном графе, как известно, называется его подграф, представляющий дерево, т.е. связной подграф, не содержащий циклов.

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

Существуют алгоритмы как выделения всех остовов дерева, так и построения кратчайшего остова. Наиболее известными из них являются алгоритмы Краскала и Прима. Алгоритм Краскала более подходящ для графа с небольшим числом ребер, алгоритм Прима — для всех других графов.

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

0 0

В основе методов, применяемых для решения перечисленных задач, лежит идея пометок вершин Дейкстра. Он впервые предложил алгоритм поиска кратчайшего пути от вершины х5 к вершине хг в графе с положительными весами дуг, т. е. когда все с, > 0. Лучший алгоритм построения кратчайших путей между всеми парами вершин принадлежит Флойду.

В ориентированном ациклическом графе, отображающем последовательности выполнения некоторого комплекса работ, предусмотренных каким либо проектом, кратчайший путь может быть найден методом динамического программирования (гл. 6, п. 6.1). Применяется он только не от последней УУ-й стадии процесса, а от первой.

Рассмотрим граф (рис. 6.15), отображающий последовательность выполнения некоторого комплекса работ. Каждая вершина графа представляет какую-то работу. Дуга от вершины х, к вершине х] проводится только тогда, когда выполнение работы, изображаемой вершины х1, по времени предшествует работе, представляемой вершиной х,-. Веса с, • > 0 — это времена задержек между работами, обусловленные длительностями их выполнения. Ими помечены дуги графа. В задаче требуется найти минимальное время, необходимое для выполнения всего комплекса работ.

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

Определим /V-шаговой процесс принятия решения как такой, на каждом шаге которого определяются максимальные пути из вершины is в остальные вершины, связанные с is либо непосредственно, либо через вершину, для которых максимальные пути из вершины is уже вычислены. Максимальный путь перемещения из вершины is в некоторую вершину j (значение функции Веллмана) обозначим Bj. Тогда функциональные уравнения, необходимые для реализации рассматриваемого метода, будут иметь вид:

Я, = 0, Bi = та х(с,. + В ), где Г (j) множество вершин, непо-

средственно предшествующих вершине/

На первом шаге непосредственную и единственную связь с вершиной is имеет вершина 1. Поскольку ci$x - 0, то В} = 0 и непосредственно предшествующая ей вершина — is.

Для вершины 2 имеем В2 = шах [(с|2 + /?,), cis2] = max [(6 + 0), 0] = 6. Непосредственно предшествующая вершина, давшая это значение, — 1.

Для вершины 3 получаем В2 = шах [(с23 + В2), с/у3] = шах [(2 + + 6), 0] = 8 с непосредственно предшествующей вершиной 3.

Далее вычисляем:

В4 = шах(с14 + Вх) - шах (6 + 0) = 6 с вершиной 1;

В5 = шах(с25 + В2) = шах (2 +6) = 8 с вершиной 2;

В6 = шах [(с46 4),(с56 + В5)] = шах [(3 + 6),(3+ 8)] = 11 с вершиной 5;

В7 = max [(с47 + В4),(с52 + В5)] = шах [(3 + 6),(3 + 8)] = 11 с вершиной 5;

В8 = max [(с38 + Я3),(с68 + В6)] = шах [(4 + 8),(3 +11)] = 14 с вершиной 6;

В9 = шах [(с79 + 57),(с89 + 58)] = max [(1 +11),(3 +14)] = 17 с вершиной 8.

Теперь определяем максимальный путь в вершину iF. Получаем Bif = max [{clip + B7),(c6iF + B6),(c9if + B9)] = max [(1 + 11), (3 + 11), (6 + 17)] = 23 с непосредственно предшествующей вершиной 9. Критический путь находится в обратном порядке по непосредственно предшествующим вершинам с наибольшими значениями В]. Его составляют следующие дуги: (1Р, 9), (9, 8), (8, 6), (6, 5), (5, 2), (2, 1), (1, /у). Записав их в прямой последовательности, получаем: (/5, 1), (1, 2), (2, 5), (5, 6), (6, 8), (8, 9), (9, />).

На рис. 6.15 критический путь обозначен жирными линиями. Значения максимальных путей В ] в вершину у из вершины /5 показаны в квадратах возле каждой вершины. Реализация метода динамического программирования в порядке возрастания стадий позволяет сразу установить реальное время начала работ В].

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

Различают два типа циклов: эйлеровы и гамильтоновы.

Эйлеров цикл в неориентированном мультиграфе — это такой цикл, который по каждому ребру проходит ровно один раз.

Гамильтонов цикл, как было определено ранее (гл. 2, п. 2.1), — это цикл, который проходит один раз через каждую вершину графа.

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

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

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

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

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

Эта задача формулируется следующим образом. Задан граф (7 = (X, Е) с истоком /5 и стоком 1р. Для каждой дуги графа (х,, х]Е задана пропускная способность qij. Потоком дуги называют величину у,.. < qjj в том случае, когда поток, втекающий в вершину, равен потоку, вытекающему из вершины, исключая исток (у и сток Требуется определить максимальный поток V как сумму потоков по дугам.

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

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

Метод решения задачи о максимальном потоке был предложен Фордом и Фалкерсоном. Затем он был существенно улучшен, в частности, советскими математиками. Самый лучший алгоритм для плотных сетей имеет оценку 0(У3).

 
< Пред   СОДЕРЖАНИЕ     След >