Пионерными в области использования теории графов в программировании были работы А.П.Ершова по организации вычисления арифметических выражений (1958 г.) и оптимальному использованию оперативной памяти (1962 г.) и заметка Р.Карпа (1960 г., на русском языке -- 1962 г.), в которой была введена в практику теоретико-графовая модель программы в виде управляющего графа, или графа переходов, ставшая к настоящему времени классической для решения задач трансляции. Эта модель оказалась чрезвычайно полезной для дальнейших исследований и практических применений в системах автоматизации, в частности для проверки правильности программ и их оптимизации, и не потеряла своей значимости при смене архитектур ЭВМ. Так, управляющий граф лежит в основе многих промежуточных представлений программ и их преобразований, используемых в векторизующих и распараллеливающих компиляторах, предназначенных для ЭВМ с параллельной архитектурой.
Наряду с управляющим графом в практике программирования широко используются другие граф-модели: граф вызовов процедур, граф зависимостей по данным, адресуемые графы данных, синтаксические деревья и деревья разбора, деревья вложенности, деревья сортировки, доминаторное и постдоминаторное деревья и т.д. К теоретико-графовым относятся и другие широко используемые в программировании модели, такие как вычислительные модели, семантические и ассоциативные сети и операторные схемы, сети Петри, R-графы Вельбицкого и другие.
В процессе чтения лекций и при написании книг мы вынуждены были оставлять в стороне массу интереснейших результатов и полезных алгоритмов, рассеянных по многочисленным источникам и часто попадавших в наши руки довольно случайным образом. Мы понимали, что их большая часть обречена на забвение ввиду невозможности перебрать все источники, где материалы могли бы быть опубликованы, и что нужно предпринимать какие-то шаги по исправлению сложившегося положения. Из обсуждения этого вопроса с А.П.Ершовым родилась идея создать энциклопедию алгоритмов на графах, сосредоточив основное внимание на тех из них, которые либо уже нашли применение в программировании, либо являются модификациями или развитием таких алгоритмов. Нам показалось естественным разбить графы на классы и объединять в одну книгу алгоритмы, разработанные для того или иного класса. Естественность этого решения, кроме всего прочего, поддерживалась наличием такого очень важного для программирования класса графов, как деревья.
Настоящая монография является первой, и надеемся, не последней книгой, написанной в плане реализации нашего проекта. Ее появлению предшествовал выход в свет двух книг, выпущенных малым тиражом в Вычислительном центре СО РАН: "Алгоритмы на деревьях" (1989 г.) и "Алгоритмы обработки деревьев" (1990 г.). Книги разошлись мгновенно, и это укрепило нашу решимость подготовить на их основе единую монографию, что мы и сделали. Мы назвали ее "Теория графов: алгоритмы обработки деревьев", а не просто "Алгоритмы на деревьях", чтобы наша книга в библиотеках не попала, как это уже имело место, в раздел "биология".
Книга предназначена не только для наведения справок о тех или иных алгоритмах, но и для знакомства с той частью теории графов, которая изучает деревья и их приложения. В ней предпринята попытка дать краткое, но по возможности полное описание основных понятий, свойств и областей применения деревьев. Мы понимаем, что в монографии представлена некоторая выборка известных к настоящему моменту алгоритмов, но надеемся, что она достаточно представительна. О существовании других алгоритмов, по разным причинам не попавших в книгу, читатель может узнать из библиографических комментариев в конце каждой главы. Последние, кроме того, позволяют читателю представить себе историю развития и нынешнее состояние той или иной проблемы теории графов и приложений. Что касается "чистой" теории графов, то здесь читателю поможет список дополнительной литературы в конце книги.
Монография состоит из 8 глав, которые объединены в три части. В части I излагаются основные понятия, свойства деревьев и такие базисные алгоритмы, как поиск в глубину, алгоритмы кодирования и генерации деревьев и т.д. В части II рассматриваются вопросы применения деревьев для решения задач, связанных со структуризацией программ, унификацией, системами переписывания термов, синтаксическим анализом и пр. Часть III посвящена вопросам хранения и поиска информации.
Книга подготовлена к изданию при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант 93-012-576) и Министерства науки, образования и технической политики (грант 2-15-2-43).