Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 17. Свойства и типы графов. других случаях полезно рассматривать неориентированный граф просто как некоторую совокупность соединений
|
|
| других случаях полезно рассматривать неориентированный граф просто как некоторую совокупность соединений. Обычно для ориентированных и для неориентированных графов (см. рис. 17.6) мы используем одно и то же представление, о чем подробно пойдет речь в разделе 17.4. Иначе говоря, в общем случае мы поддерживаем два представления каждого ребра неориентированных графов, каждое из них указывает в одном из направлений, так что мы имеем возможность сразу же ответить на вопросы типа " Какие вершины соединены с вершиной v? " |
вестных еще как орграфы (orgcaph), ребра однонаправленные: мы рассматриваем пару вершин, определяющую конкретное ребро, как упорядоченную {ordered) пару, которая определяет однонаправленную смежность в том смысле, что возможность перехода из первой вершины во вторую отнюдь не означает переход из второй вершины в первую. Многие применения (например, графы, представляющие Web, графы, используемые при составлении расписаний, или графы, применяемые для обработки телефонных звонков) естественным образом описываются в виде орграфов.
Ребра в орграфах мы называем ориентированными ребрами (directed edges), хотя в общем случае это свойство вытекает из контекста (некоторые авторы для обозначения ориентированных ребер применяют термин дуга (arc)). Первая вершина ориентированного ребра называется началом (source); вторая вершина называется концом (destination). (Некоторые авторы употребляют, соответственно, термины хвост (tail) и голова (head), чтобы отличить вершины ориентированного графа, однако мы будем избегать таких обозначений, поскольку мы употребляем эти же термины при реализации структур данных.) На диаграммах мы изображаем ориентированные ребра в виде стрелок, направленных из начала в конец, и часто говорим, что ребро указывает (points) на ту или иную вершину. Когда мы используем обозначение w-v по отношению к орграфу, мы делаем это с целью показать, что ребро, которое исходит из w и заходит в v, отличается от ребра v-w, которое исходит из v и заходит в w. Мы также говорим о полустепени исхода (outdegree) и полустепени захода (indegree) некоторой вершины (соответственно, число ребер, для которых она служит началом, и число ребер, для которых она служит концом).
Иногда целесообразно рассматривать неориентированный граф как орграф, у которого имеются два ориентированных ребра (по одному в каждом направлении); в
РИСУНОК 17.6. ДВА ОРГРАФА
Чертеж вверху есть представление графа, приведенного в качестве примера на рис. 17.1, интерпретируемое как ориентированный граф, при этом мы рассматриваем ребра как упорядоченные пары и изображаем их в виде стрелок, ведущих из первой вершины во вторую. Этот граф является DAG-графом. Чертеж в нижней части рисунка — это представление неориентированного графа, показанного на рис. 17.1, который может служить иллюстрацией способа, обычно выбираемого нами для представления неориентированных графов: в виде орграфа, в котором каждому соединению соответствуют два ребра (по одному в каждом направлении).
Часть 5. Алгоритмы на графах
Глава 19 посвящена изучению структурных свойств орграфов; в общем случае они более сложные, чем соответствующие свойства неориентированных графов. Направленный цикл (directed cycle) в орграфе — это цикл, в котором пары смежных вершин появляются в порядке, указанном (устанавливаемом) ребрами графа. Граф DAG (Directed Acyclic Graph - ориентированный ациклический граф) есть орграф, который не содержит направленных циклов. DAG-граф (ациклический орграф) и дерево (ациклический неориентированный граф) - это отнюдь не тождественные понятия. Иногда мы обращаемся к базовому неориентированному графу (underlying undirected graph), лежащему в основе орграфа, подразумевая под ним неориентированный граф, определяемый тем же множеством ребер, при этом, однако, эти ребра не рассматриваются как ориентированные.
В главах 20-22 содержится главным образом анализ алгоритмов решения различных вычислительных задач, связанных с использованием графов, в которых в виде вершин и ребер представлена другая информация. В случае взвешенного графа (weighted graph) с каждым ребром мы связываем числа (weights — веса), которые в общем случае представляют собой расстояние либо стоимость. Мы Также можем присвоить вес каждой вершине либо несколько весов каждой вершине и каждому ребру. В главе 20 мы будем изучать взвешенные неориентированные графы, которые мы обычно называем сетями (networks). Алгоритмы в главе 22 решают классические задачи, которые возникают в конкретных интерпретациях сетей, известных как транспортные сети (flow network).
Уже из главы 1 стало ясно, что комбинаторная структура графа получила широкое распространение. Масштаб распространения этой структуры тем более поразителен в связи с тем, что начало ей дала простая математическая абстракция. Эта лежащая в основе простота отражается во многих программных кодах, которые мы разрабатываем для базовой обработки графов. Тем не менее, такая простота часто заслоняет собой сложные динамические свойства, которые требуют глубокого понимания комбинаторных свойств самих графов. Зачастую очень трудно убедить самих себя в том, что алгоритм работает на графе в соответствии с замыслом, поскольку программа получается настолько компактной, что в это даже трудно поверить.