Предисловие

Хотя первая книга по теории графов появилась в 1935 г., началом широкого внедрения методов теории графов в практику научных и технических исследований можно считать 50-е гг. Книги по теории графов (К. Берж, Р. Басакер и Т. Саати), вышедшие в начале 60-х гг., уже содержали материалы, описывающие приложения теории графов в исследовании операций, дискретной оптимизации, электротехнике и пр. Затем исследовали книги, целиком посвященные вопросам применения теории графов в отдельных областях знаний, в том числе в программировании. Среди них можно назвать ``Введение в теоретическое программирование. Беседы о методе'' А.П. Ершова (1977 г.), ``Применение теории графов в программировании'' В.А. Евстигнеева (1985 г.), ``Оптимизирующие преобразования программ'' В.Н. Касьянова (1988 г.), ``Комбинаторика для программистов'' В. Липского (1988 г.). В этих книгах был обобщен и систематизирован громадный опыт использования теоретико-графовых методов для анализа, оптимизации и преобразования программ, организации вычислительных процессов, оценки сложности программ и пр.

Пионерными в области использования теории графов в программировании были работы А.П. Ершова по организации вычисления арифметических выражений (1958 г.) и оптимальному использованию оперативной памяти (1962 г.) и заметка Р. Карпа (1960 г., на русском языке -- 1962 г.), в которой была введена в практику теоретико-графовая модель программы в виде управляющего графа, или графа переходов, ставшая к настоящему времени классической для решения задач трансляции. Эта модель оказалась чрезвычайно полезной для дальнейших исследований и практических применений в системах автоматизации, в частности для проверки правильности программ и их оптимизации, и не потеряла своей значимости при смене архитектур ЭВМ. Так, управляющий граф лежит в основе многих промежуточных представлений программ и их преобразований, используемых в векторизующих и распараллеливающих компиляторах, предназначенных для ЭВМ с параллельной архитектурой.

Наряду с управляющим графом в практике программирования широко используются другие граф-модели: граф вызовов процедур, граф зависимостей по данным, адресуемые графы данных, синтаксические деревья и деревья разбора, деревья вложенности, деревья сортировки, доминаторное и постдоминаторное деревья и т.д. К теоретико-графовым относятся и другие широко используемые в программировании модели, такие как вычислительные модели, семантические и ассоциативные сети и операторные схемы, сети Петри, R-графы Вельбицкого и другие.

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

Настоящая монография является первой, и надеемся, не последней книгой, написанной в плане реализации нашего проекта. Ее появлению предшествовал выход в свет двух книг, выпущенных малым тиражом в Вычислительном центре СО РАН: ``Алгоритмы на деревьях'' (1989 г.) и ``Алгоритмы обработки деревьев'' (1990 г.). Книги разошлись мгновенно, и это укрепило нашу решимость подготовить на их основе единую монографию, что мы и сделали. Мы назвали ее ``Теория графов: алгоритмы обработки деревьев'', а не просто ``Алгоритмы на деревьях'', чтобы наша книга в библиотеках не попала, как это уже имело место, в раздел ``биология''.

Книга предназначена не только для наведения справок о тех или иных алгоритмах, но и для знакомства с той частью теории графов, которая изучает деревья и их приложения. В ней предпринята попытка дать краткое, но по возможности полное описание основных понятий, свойств и областей применения деревьев. Мы понимаем, что в монографии представлена некоторая выборка известных к настоящему моменту алгоритмов, но надеемся, что она достаточно представительна. О существовании других алгоритмов, по разным причинам не попавших в книгу, читатель может узнать из библиографических комментариев в конце каждой главы. Последние, кроме того, позволяют читателю представить себе историю развития и нынешнее состояние той или иной проблемы теории графов и приложений. Что касается ``чистой'' теории графов, то здесь читателю поможет список дополнительной литературы в конце книги.

Монография состоит из 8 глав, которые объединены в три части. В части I излагаются основные понятия, свойства деревьев и такие базисные алгоритмы, как поиск в глубину, алгоритмы кодирования и генерации деревьев и т.д. В части II рассматриваются вопросы применения деревьев для решения задач, связанных со структуризацией программ, унификацией, системами переписывания термов, синтаксическим анализом и пр. Часть III посвящена вопросам хранения и поиска информации.

Книга подготовлена к изданию при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант 93-012-576) и Министерства науки, образования и технической политики (грант 2-15-2-43).