Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Орграфы и ориентированные ациклические графы
|
|
| Е |
сли мы предаем значение, в каком порядке описываются две вершины каждого ребра графа, мы получаем совершенно другой комбинаторный объект, известный как ориентированный граф (directed graph), или орграф (digraph). На рис. 19.1 показан пример орграфа. В орграфах обозначение s-t описывает ребро, которое ведет из вершины s в вершину t, но при этом оно не дает никакой информации о том, существует ли ребро, ведущее из / в s. Имеется четыре вида отношений, в которых могут находиться две любые вершины орграфа: связывающее их ребро отсутствует, ребро s-t, ведущее из s в t, ребро t-s, ведущее из / в s, и два ребра s-t и t-s, которые указывают на наличие связи в обоих направлениях. Требование однонаправленности естественно для многих приложений, оно легко реализуется в разрабатываемых нами программах и представляется нам безобидным, однако оно влечет за собой появление новой комбинаторной структуры, которая оказывает глубокое воздействие на наши алгоритмы; в силу присущих ей свойств работа с орграфами существенно отличается от работы с неориентированными графами. Обработку орграфов можно сравнить с ездой по городу, в котором все улицы имеют односторонне движение, и при этом направление движения не указано с помощью какого-нибудь унифицированного способа. Можно себе представить, какие приключения нас ожидают, если в подобной ситуации мы вознамеримся проехать из одной точки города в другую.
Направления ребер в графе мы интерпретируем различными способами. Например, при построении графа телефонных вызовов можно принимать за направление ребра направление от вызывающего абонента к абоненту, принима-
Часть 5. Алгоритмы на графах
| каждой из этих работ, чтобы ни одно из отношений предшествования не было нарушено? В этом заключается суть проблемы, известной как задача составления расписаний (scheduling problem). Она не имеет смысла, если в орграфе имеется цикл, в подобного рода ситуациях мы работаем с графами DAG (directed acyclic graph — ориентированный ациклический граф). В разделах 19.5—19.7 мы рассмотрим базовые свойства графа DAG и алгоритмы решения простой задачи, получившей название топологической сортировки (topological sorting). На практике при решении задач составления расписаний в общем случае учитывается вес вершин или ребер, которые моделируют время или стоимость каждой работы. Такие задачи мы будем изучать в главах 21 и 22. Число возможных орграфов поистине огромно. Каждое из возможных V2 ориентированных ребер (в том числе петли) может входить в график или не входить в него, таким образом, общее число разных орграфов равно 2V. Как показано на рис. 19.2, с увеличением числа вершин это число стремительно возрастает, даже по сравнению с числом различных неориентированных графов, уже при небольших значениях V. Как и в случае неориентированных графов, число изоморфных друг другу классов (вершины одного из изоморфных графов можно переименовать таким образом, чтобы получить график, идентичный другому) намного меньше, однако мы не можем извлечь для себя конкретную пользу из подобного сокращения числа графов, поскольку нам неизвестен достаточно эффективный алгоритм выявления изоморфных графов. |
ющему вызов. В графе финансовых операций можно применять тот же принцип, при этом ребро представляет собой финансовые средства, товары или информацию, передаваемые от одного агента другому. Мы можем найти подходящий пример, соответствующий этой классической модели в Internet; в этом случае вершины представляют Web-страницы, а ребра — ссылки между страницами. В разделе 19.4 мы рассмотрим другие примеры; большая их часть моделирует ситуации с большей степенью абстракции.
Довольно часто приходится сталкиваться с ситуациями, когда направление ребра отражает отношение предшествования. Например, орграф может моделировать производственную линию: вершины обозначают работу, которую необходимо выполнить, при этом существует ребро, ведущее из вершины s в вершину /, если работа, соответствующая вершине s, должна быть выполнена, прежде чем может быть выполнена работа, соответствующая вершине t Другой способ моделирования той же ситуации заключается в использовании диаграммы PERT (PERT, Project Evaluation and Review Technique — сетевое планирование и управление): ребра представляют работы, а вершины неявно описывают отношение предшествования (все работы, сходящиеся в конкретной вершине, должны быть завершены, прежде чем начнутся работы, исходящие из этой вершины). Какие следует принимать решения относительно сроков выполнения
РИСУНОК 19.1. ОРИЕНТИРОВАННЫЙ ГРАФ (ОРГРАФ)
Орграф определяется списком вершин и ребер (внизу), при этом порядок, в котором мы перечисляем вершины при описании ребра, показывает, что ребро направлено из первой вершины во вторую. На чертежах орграфа для изображения ориентирован-ных ребер (сверху) используются стрелки.