Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 17, Свойства и типы графов
|
|
контекст для изучения широкого набора алгоритмов на графах, от простейших, описанных в части 1, до очень сложных, описываемых в главах 18-22.
Как всегда, мы хотим знать, какой из возможных алгоритмов решения конкретной задачи обладает максимальной эффективностью. Задача изучения рабочих характеристик алгоритмов на графах представляет собой достаточно сложную проблему, что можно объяснить следующими причинами:
■ Стоимость алгоритма зависит не только от свойств множества элементов, но так
же и от многочисленных свойств соединений (и глобальных свойств графа, обус
ловленных свойствами соединений).
■ Трудность разработки точных моделей типов графов, с которыми, возможно, при
дется столкнуться.
Мы часто исходим из предположения, что используемым алгоритмам на графах придется работать в условиях, наиболее неблагоприятных для их рабочих характеристик, даже если во многих случаях на практике такие предположения представляют собой пессимистическую оценку. К счастью, как мы убедимся далее, многие из этих алгоритмов оптимальны и не требуют больших непроизводительных затрат. В отличие от них, существуют алгоритмы, которые затрачивают одинаковые ресурсы на обработку всех графов заданного размера. Мы можем с достаточной степенью точности предсказать, как поведут себя такие алгоритмы в конкретных условиях. В тех случаях, когда такие предсказания невозможны, нам придется уделить особое внимание свойствам графов различных типов, которые, в соответствии с нашими ожиданиями, проявятся в конкретных практических ситуациях, и оценить, как эти свойства могут повлиять на производительность выбранных алгоритмов.
Мы начнем с изучения основных определений графов и свойств графов, а также с освоения стандартной терминологии, которая используется для их описания. Затем мы дадим определения интерфейсов АТД (ATD, abstract data type — абстрактный тип данных), которыми будем пользоваться при изучении алгоритмов на графах, двух наиболее важных структур данных, применяемых для представления графов — матрицы смежности (adjacency-matrix) и списков смежных вершин (adjacency-lists), а также различных подходов к реализации базовых функций над абстрактными типами данных (АТД-функций). Затем мы рассмотрим клиентские программы, способные строить случайные графы, которые могут использоваться для тестирования разработанных алгоритмов и для изучения свойств графов. Весь этот материал служит фундаментом, позволяющим применять алгоритмы обработки графов для решения трех классических задач, связанных с поиском путей в графах, которые служат также иллюстрацией того, что по сложности задачи обработки графов существенно отличаются друг от друга даже в тех случаях, когда различия между ними далеко не очевидны. Эта глава завершается обзором наиболее важных задач обработки графов, которые будут рассматриваться в этой книге, в контексте сложности их решения.
Часть 5. Алгоритмы на графах
17.1. Глоссарий
С графами связана обширная терминология. Большинство употребляемых терминов имеют прямое определение, и для удобства ссылок целесообразно рассматривать их в каком-то одном месте, а именно, в данном разделе. Некоторые из понятий мы уже употребляли в главе 1 при изучении базовых алгоритмов, другие останутся невостребованными до тех пор, пока мы не перейдем к изучению соответствующих им новейших алгоритмов в главах 18-22.
Определение 17.1. Граф есть некоторое множество вершин и некоторое множество ребер, соединяющих пары различных вершин (одно ребро может соединять максимум одну пару вершин).
Мы используем цифры от 0 до V-1 в качестве имен вершин графа, состоящего из V вершин. Основная причина выбора именно этой системы обозначений заключается в том, что мы получаем быстрый доступ к информации, соответствующей каждой вершине, путем индексирования векторов. В разделе 17.6 будет рассмотрена программа, которая применяет таблицу идентификаторов с тем, чтобы установить отображение " один-к-одному" с целью связать V произвольных имен с вершин с V целыми числами в диапазоне от 0 до V-1. Имея в своем распоряжении такую программу, мы можем употреблять индексы как имена вершин (для удобства обозначений) без ущерба для универсальности рассуждений. Иногда мы будем предполагать, что множество вершин определено неявно, взяв за основу для определения графов множество ребер и учитывая только те вершины, которые закреплены, по меньшей мере, за одним ребром. Во избежание громоздких выражений, как то: " граф, состоящий из 10 вершин со следующим набором ребер", мы часто явно не указываем числа вершин, если оно следует из контекста. Далее будем придерживаться соглашения, в соответствии с которым число вершин в заданном графе всегда обозначается через К, а число ребер - через Е.
В качестве стандартного определения графа (с которым первый раз довелось столкнуться в главе 5) будет принято определение 17.1, но при этом заметим, что в нем использованы два технических упрощения. Во-первых, оно не позволяет дублировать ребра (математики иногда называют такие ребра параллельными (parallel), а граф, который может содержать такие ребра, мультиграфом (multigraph)). Во-вторых, оно не допускает ребер, замыкающихся на одну и ту же вершину; такое ребро называются петлей {self-loop). Графы, в которых нет параллельных ребер или петлей, иногда называют простыми графами (simple graph).
Мы употребляем понятия простых графов в формальных определениях, поскольку таким путем легче выразить их основные свойства, а также ввиду того, что параллельные ребра и петли во многих приложениях не нужны. Например, мы можем ограничить число ребер простого графа заданным числом вершин.
Свойство 17.1. Граф, состоящий из V вершин, содержит не более V(V — I)/2 ребер.
Доказательство: Общее число возможных пар вершин равно К2, в том числе V петель, при этом связи между различными вершинами учитываются дважды, следовательно, максимальное число ребер не превосходит значения (V2 - V)/2 = V(V- l)/2. ■