Читать онлайн «Теория графов, алгоритмы обработки деревьев»

В. А. Евстигнеев В. Н. Касьянов алгоритмы обработки деревьев РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ СИСТЕМ ИНФОРМАТИКИ В. А. Евстигнеев В. Н. Касьянов ТЕОРИЯ ГРАФОВ АЛГОРИТМЫ ОБРАБОТКИ ДЕРЕВЬЕВ Ответственный редактор член-корреспондент РАН В. Е. К о т о в ВО "НАУКА" НОВОСИБИРСК 1994 УДК 519. 1 +519. 683 ББК 32. 811 Е26 Теория графов: алгоритмы обработки деревьев / В. А. Евстигнеев, В. Н. Касьянов. — Новосибирск: ВО "Наука". Сибирская издательская фирма, 1994. — 360 с. ISBN 5—02—030332— 1. Книга представляет собой справочник программиста и содержит систематическое изложение алгоритмов на деревьях, образующих один из наиболее важных и широко используемых в программировании классов алгоритмов теории графов. Даны основные математические понятия и модели, методы и алгоритмы, связанные с различными приложениями теории графов. Рассмотрены задачи обходов и генерации деревьев, отыскания каркасов, построения структурных деревьев, изоморфизма, унификации и преобразования деревьев, организации и представления информации, а также синтаксического анализа. Для специалистов по теории графов, системных и прикладных программистов, а также для специалистов по САПР, конструкторов СБИС. Табл. 5. Ил. 185. Библиогр. : 351 назв. Рецензенты доктора физико-математических наук В. К. Попков, И. В. Поттосин Утверждено к печати Институтом систем информатики СО РАН Справочное издание Евстигнеев Владимир Анатольевич Касьянов Виктор Николаевич Теория графов алгоритмы обработки деревьев Редактор Л. П. Голышева Художественный редактор Л. В. Матвеева Художник В. А Аксенов Технический редактор Н. М. Остроумова Операторы набора Л. К. Грушецкая, П. В. Карповская Операторы электронной верстки Л. Н. Демина, О В. Дробышевич ИБ № 51040 ЛР N° 020297 от 27. 11. 91. Сдано в набор 05. 03. 93. Подписано в печать 21. 12. 93. Бумага тип № 2. Формат 60x90Vl6- Гарнитура тайме. Офсетная печать Усл. печл. 22,5. Уч. -изд. л. 21,9. Тираж 660 экз. Заказ № 537. Ордена Трудового Красного Знамени ВО "Наука", Сибирская издательская фирма. 630099 Новосибирск, ул. Советская, 18. Оригинал-макет подготовлен в Институте систем информатики СО РАН. Новосибирская типография № 4 ВО "Наука". 630077 Новосибирск, ул. Станиславского, 25. Е 11°А0^?00^005К:Б—6—44—1993 © В. А. Евстигнеев, В. Н. Касьянов, 1994 042(02)-94 ISBN 5—02—030332—1 ©Российская Академия наук, 1994 Светлой памяти Андрея Петровича Ершова посвящается ПРЕДИСЛОВИЕ Хотя первая книга по теории графов появилась в 1935 г. , началом широкого внедрения методов теории графов в практику научных и технических исследований можно считать 50-е гг. Книги по теории графов (К. Берж, Р. Басакер и Т. Саати), вышедшие в начале 60-х гг. , уже содержали материалы, описывающие приложения теории графов в исследовании операций, дискретной оптимизации, электротехнике и пр. Затем последовали книги, целиком посвященные вопросам применения теории графов в отдельных областях знаний, в том числе в программировании. Среди них можно назвать "Введение в теоретическое программирование.