На этом шаге мы приведем общие сведения о графах.

Сложность получения ответа на тот или иной вопрос относительно алгоритмических или структурных свойств данного графа зависит, естественно, от программного способа представления графа. Поэтому в алгоритмах на графах взаимосвязь "Алгоритм + Структура данных" проявляется весьма сильно. Один и тот же алгоритм, реализованный на различных структурах данных, часто приводит к:

(1) различным по размеру программам;
(2) повышению эффективности алгоритма.

Однако, переход от одного представления к другому относительно прост и может быть выполнен за O(|V|²) операций, где |V| - количество вершин графа [Рейнгольд,Нивергельт,Део,1980,с.355]. Поэтому если решение задачи на графе обязательно требует числа операций, по крайней мере пропорционального |V|², то время её решения не зависит от способа представления графа, т.к. оно может быть изменено за O(|V|²) операций.

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

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

Замечания.

В качестве введения в комбинаторные алгоритмы можно рекомендовать [1, 2, 3, 4, 5, 6, 7].
При написании данного раздела были существенно использованы результаты, изложенные в монографии [8, гл. 4]. Мы лишь адаптировали их к языку Haskell с исправлением единственной опечатки в функции SP!_DF [8, c.130-131].

⁽¹⁾Оре О. Графы и их применение. - М.: Мир, 1965. - 175 с.
⁽²⁾Харари Ф. Теория графов. - М.: Мир, 1973. - 300 с.
⁽³⁾Уилсон Р. Введение в теорию графов. - М.: Мир, 1977. - 208 с.
⁽⁴⁾Рейнгольд Э., Hивергельт Ю., Део H. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 с.
⁽⁵⁾Пападимитриу Х., Стайнглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. - 512 с.
⁽⁶⁾Касьянов В.H., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986. - 272 с.
⁽⁷⁾Липский В. Комбинаторика для программистов. - М.: Мир, 1988. - 213 с.
⁽⁸⁾Крюков А.П., Радионов А.Я., Таранов А.Ю., Шаблыгин Е.М. Программирование на языке R-Лисп. - М.: Радио и связь, 1991. - 192 с.

На следующем шаге мы рассмотрим матрицу смежности.

Предыдущий шаг Содержание Следующий шаг