Обзор основных задач теории графов

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

Быстрый поиск по дереву. Часто графовая модель представляет собой дерево (см. рис. 4.4). К модели в форме дерева приводят задачи структуризации данных в базах данных или знаний в базах знаний. В задаче принятия решений множество возможных решений моделируется деревом решений.

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

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

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

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

Расчет (анализ) сетевого графика. Пусть имеется некоторый план работ (строительство, регламентные работы, производство, технологический процесс и т. д.). Этот план моделируется графом, приведенным на рис. 4.7.

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

Каждая дуга нагружена числом — временем, необходимым на выполнение этой операции.

Ставятся следующие задачи:

1) отыскание минимального времени выполнения всего проекта (критического времени);

2) отыскание тех операций, которые существенно влияют на критическое время; их совокупность образует так называемый критический путь;

3) отыскание резервов времени.

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

Рассматривается следующая задача коммивояжера (для продавца, купца, коробейника).

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

Определение 4.4. Замкнутый обход симметричного мультиграфа по всем вершинам по одному разу называется гамилътоновым циклом. Замкнутый обход мультиграфа по всем ребрам по одному разу называется эйлеровым циклом.

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

Замечание 4.1. В XVIII в. Л. Эйлер занимался следующей задачей поиска в мультиграфе пути, который был назван в честь него эйлеровым циклом.

Рис . 4. 11. Два острова реки Прегаль и семь мостов (1 –7 )

В г. Кенигсберге (Калининграде) протекает река Прегаль, на которой имеются два острова, соединенные семью мостами с берегами реки и друг с другом (рис. 4.11).

Л. Эйлер, гуляя в этой местности, заинтересовался следующей задачей.

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

Систему мостов здесь молено изобразить в виде мультиграфа так, что мосты это дуги графа, а вершины — острова и берега (рис. 4.12).

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

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

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

Рис . 4. 12. Мультиграф, дуги которого изображают мосты

Рис . 4. 13. Мультиграф, вершины которого мосты

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

Задача о максимальном потоке. Это может быть задача о пересылке максимума товаров (сырья, информации и т.п.) по транспортной сети (см. рис. 4.5).

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

Выбираются два города. Один — пункт отправления A , другой — пункт назначения В.

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

Алгоритм решения задачи о максимальном потоке носит имя двух его авторов и называется алгоритмом Форда-Фалкерсона.

Анализ процесса смены состояний в системе массового обслуживания (марковский процесс). Рассмотрим граф, приведенный на рис. 4.6. Здесь нагрузками на дугах являются вероятности перехода из одного состояния в другое. Требуется найти вероятности нахождения СМО в каждом состоянии. Для этого составляются и решаются дифференциальные уравнения А. Н. Колмогорова на такие вероятности.

Далее, найдя, например, вероятность нахождения системы в состоянии q 0, будем знать вероятность простоя СМО. Найдя вероятность , будем знать вероятность отказа клиенту. Зная вероятности нахождения СМО в каждом состоянии, можно найти усредненные характеристики СМО. Например, среднее число клиентов в СМО (математическое ожидание), среднее время обслуживания клиента и т. д.

Расчет сетевого графика

Разберем подробно метод решения одной из задач теории графов. Рассмотрим сетевой график (см. рис. 4.7).

Определение 4.5. Сетевым графиком называется ориентированный граф Г = á X , R ñ с неотрицательной числовой нагрузкой на каждой дуге ( xi, xj) = uij∈ R . Нагрузку на дуге обозначим T ( uij) ≥ 0. Кроме того, в сетевом графике еще предполагаются три условия.

1. Во множестве вершин X имеются две вершины х 0и х k, такие, что из вершины х 0дуги только выходят, а в вершину х kдуги только входят. Вершина х 0называется начальной, а вершина х k— конечной вершиной сетевого графика.

2. Для всякой промежуточной вершины х i, т. е. не являющейся ни начальной, ни конечной, существуют два пути в сетевом графике от начальной вершины до рассматриваемой L (х 0, х i) и от рассматриваемой вершины до конечной L (х i, х k).

3. В сетевом графике нет циклов.

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

Пример 4. 6. Рассмотрим сетевой график работ, приведенный на рис. 4.14. Изобразим его так, чтобы в каждой вершине графика можно было написать необходимые числовые показатели. Анализ технологического процесса предполагает построение его сетевого графика, т. е. модели процесса и расчет основных показателей такого графика.

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒