Введение

Современное состояние программирования нельзя представить себе без теоретико-графовых алгоритмов. Хорошо известно, что многие задачи повышения качества трансляции как в смысле улучшения рабочих характеристик транслятора, так и в смысле повышения качества получаемых машинных программ формулируются и решаются как задачи на графах. Сюда относятся в первую очередь задачи, связанные с представлением программ в виде теоретико-графовых моделей, важнейшей из которых является управляющий граф. Кроме того, необходимо указать на такие области применения граф-моделей, как эффективное использование ресурсов вычислительной системы (оптимизация использования памяти, регистров, уменьшение обменов между оперативной и внешней памятью и т.д.), организация больших массивов информации (деревья и, вообще, графы данных для повышения эффективности информационного поиска), увеличение степени параллелизма программы, повышение эффективности работы многопроцессорных и многомашинных систем (распределение загрузки процессоров, обмен сообщениями между процессами, синхронизация, конфигурация сетей связи между процессорами и т.д.). Решение этих и подобных задач привело к появлению множества граф-моделей, связанных как с программами и структурами данных, так и с вычислительными системами, в том числе параллельными.

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

Теория графов из академической дисциплины все более превращается в средство, владение которым становится решающим для успешного применения компьютеров во многих прикладных областях. Несмотря на наличие обширной специальной литературы по решению задач на графах, широкое применение в практике программирования полученных математических результатов затруднено в силу отсутствия систематического их описания, ориентированного на программистов. Поэтому значительный класс практических задач, по существу сводящихся к простому выбору подходящего способа решения и к построению конкретных формулировок абстрактных алгоритмов, для многих программистов все еще остается полем для интеллектуальной деятельности по ``переоткрытию'' методов. Даже известный фундаментальный труд Д. Кнута ``Искусство программирования для ЭВМ'', если бы он и продолжился, как планировалось, не сможет решить эту проблему в силу ориентации Д. Кнута на низкоуровневое (в терминах машины MIX) описание алгоритмов. В изданных же трех томах серии излагается достаточно узкий класс используемых в программировании граф-моделей (фактически Д. Кнут ограничился рассмотрением деревьев и уже не планирует продолжать работу над серией).

Предлагаемая вниманию читателя книга является одной из первых попыток систематизации знаний по алгоритмам теории графов для программиста.

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

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

Заметим, что любая из книг, содержащих теоретико-графовые алгоритмы, оставалась либо книгой по теории графов, либо книгой по основной предметной области, использующей теоретико-графовые методы. Развивая эту тематику, мы решили объединить в одной книге графовые алгоритмы решения для графовых задач, и задачи по программированию вместе со специфическими алгоритмами их решения, основанными или использующими теоретико-графовые методы и алгоритмы. Этот подход подсказал нам идею разбить всё множество графов, которые наиболее часто встречаются в практике решения задач программирования, на классы, объединив вокруг каждого такого класса соответствующие задачи из информатики и программирования. Такими классами выступили классы деревьев, бесконтурных (или ациклических) графов и сводимых (или регуляризуемых) графов. Заметим, что последние два класса относятся к ориентированным графам, а из класса деревьев используется подкласс корневых деревьев, что также относится к ориентированным графам. Данный подход был успешно реализован нами в книгах ``Теория графов: алгоритмы обработки деревьев'' (1994 г.), ``Теория графов: алгоритмы обработки бесконтурных графов'' (1998 г.), ``Сводимые графы и граф-модели в программировании'' (1999 г.) и ``Толковый словарь по теории графов и ее применению в информатике и программировании'' (1999 г.). Однако небольшой тираж этих книг сделал их недоступными студентам и специалистам по программированию.

Предлагаемая книга объединяет и существенно расширяет материал перечисленных книг, что позволит более эффективно использовать предлагаемые методы и алгоритмы. Впервые в отечественной литературе в ней дается монографическое изложение материала по вопросам рисования графов и визуальной обработки графовых моделей.

Книга состоит из 12-ти глав и 2-х приложений, образующих три части.

Часть I посвящена обработке и визуализации графов. Основная задача этой части, состоящей из пяти глав, -- описать базовые модели и алгоритмы, связанные с применением теории графов в программировании, включая вопросы визуализации и рисования графов. Изложение материала привязано к трём основным типам графов: деревья, дэги или бесконтурные графы и сводимые или регуляризуемые графы. Отдельно рассматриваются основные теретико-графовые понятия и методы рисования и визуальной обработки графовых моделей.

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

Часть III содержит справочный материал и состоит из двух приложений. Приложение 1 посвящено ``переборным'' (NP-полным) задачам, в котором наряду с введением понятия NP-полноты и рассмотрением списков NP-полных задач из различных областей программирования и информатики, описываются РАМ и ВУ-язык, используемые в книге для представления и анализа алгоритмов. В приложении 2 приведены характеристики размещений графов, включая размер области размещения, оценки величины углов, число сгибов и пр.

Формулировки основных свойств получают буквенные обозначения (А, Б, В, Г и т.д.) внутри каждого раздела, и ссылка на свойство в тексте образуется из номера раздела и его буквенного обозначения, например, свойство 1.2.3, А указывает на свойство А из раздела 1.2.3. Если производится ссылка на свойство в том же разделе, то номер раздела может опускаться.

Рисунки в книге выполнены авторами с использованием системы для работы с графами HIGRES.

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

Монография основывается на работах авторов в рамках проектов, которые выполнялись в лаборатории конструирования и оптимизации программ Института систем информатики Сибирского отделения Российской академии наук (ИСИ СО РАН) и на кафедре программирования Новосибирского государственного университета (НГУ) при финансовой поддержке Российского фонда фундаментальных исследований (РФФИ) и Минобразования. Авторы благодарны всем коллегам, принимавшим участие в выполнении этих проектов, в первую очередь И.А. Лисицыну, Е.С. Мердишевой, Т.С. Мердишевой, В.Е. Казанцеву, Д.Е. Бабурину и И.Л. Мирзуитовой.

Нельзя не назвать и тех, кто своими работами, советами и поддержкой способствовал появлению этой книги. Прежде всего -- это А.П. Ершов, С.С. Лавров, А.А. Летичевский, Э.З. Любимский, В.Е. Котов, В.К. Попков и А.А. Берс. Всем им, а также И.П. Мелинг и Л.К. Грушецкой, оказавшим большую помощь в технической подготовке рукописи, авторы выражают искреннюю признательность.

Наконец авторы благодарят своих жен (Светлану Николаевну и Людмилу Анатольевну) и детей (Елену Викторовну, Александра Владимировича и Надежду Владимировну) за любовь и поддержку при работе над книгой (Светлана Николаевна также помогла нам с подготовкой большинства иллюстраций). Любовь, терпение и поддержка наших близких сделали эту книгу возможной, им она и посвящается.

Книга такого объема не может не содержать ошибки. Мы будем благодарны за любые замечания и пожелания. Присылайте их нам по адресу: ИСИ СО РАН, Новосибирск, 630090. Можно также получить список известных опечаток и сообщить о найденных ошибках по электронной почте и на страницах Web-сайта лаборатории конструирования и оптимизации программ ИСИ СО РАН. Чтобы получить инструкции, по адресу graphs@pco.iis.nsk.su отправьте письмо, содержащее слово Help в качестве темы письма. Извините, если мы не сможем лично ответить на все письма.

Книга предназначена для широкого круга специалистов, использующих методы теории графов при решении своих задач, в первую очередь для системных и прикладных программистов, а также для специалистов по системам автоматизации проектирования (САПР), конструкторов сверх больших интегральных схем (СБИС) и т.д. Она может быть использована в качестве учебного пособия студентами высших учебных заведений, аспирантами и преподавателями, читающими соответствующие курсы. В принципе книга самодостаточна, т.е. содержит весь необходимый материал, всё же желательно предварительное знакомство с основами теории графов и программирования.