Введение

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

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

Теория графов из академической дисциплины все более превращается в средство, владение которым становится решающим для успешного применения компьютеров во многих прикладных областях. Несмотря на наличие обширной специальной литературы по решению задач на графах, широкое применение в практике программирования полученных математических результатов затруднено в силу отсутствия систематического их описания, ориентированного на программистов. Поэтому значительный класс практических задач, по существу сводящихся к простому выбору подходящего способа решения и к построению конкретных формулировок абстрактных алгоритмов, для многих программистов все еще остается полем для интеллектуальной деятельности по “переоткрытию” методов. Даже известный фундаментальный труд Д. Кнута “Искусство программирования для ЭВМ”, если бы он и продолжился, как планировалось, не сможет решить эту проблему в силу ориентации Д. Кнута на низкоуровневое (в терминах машины 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 в качестве темы письма. Извините, если мы не сможем лично ответить на все письма.

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