От редактора перевода
Книга Басакера и Саати «Конечные графы и сети» рассчитана на лиц, занимающихся использованием теории графов при решении различных задач в области техники, экономики, социологии. Она содержит основные понятия теории графов, достаточно полный перечень научных результатов и описание методов решения различных задач.
Для лучшего понимания и усвоения материала в книге приводится большое число примеров, а также имеются учебные упражнения.
Следует заметить, что книга в целом написана не везде ровно и наряду с элементарными с элементарными сведениями приводятся данные, требующие от читателя солидной математической подготовки.
Перевод книги представлял известные трудности. В русской литературе до настоящего времени отсутствует единая терминология по теории графов, и переводчикам в процессе работы над книгой пришлось приложить много труда при выборе терминов. Дополнительные трудности возникли в связи с тем, что терминология авторов далеко не бесспорна.
В процессе перевода поддерживался контакт с авторами, что позволило уточнить ряд мест. Кроме того, исправлены имевшиеся в оригинале неточности и опечатки.
Несмотря на то, что с момента выхода книги на английском языке прошло относительно длительное время, можно надеяться, что ее русское издание окажется полезным для широкого круга лиц, занимающихся прикладными математическими вопросами, инженеров и экономистов.
А. Тейман
Предисловие
Теория графов дает простой, доступный и мощный инструмент построения моделей и решения задач упорядочения объектов. В настоящее время существует множество проблем, где требуется построить некоторые сложные системы с помощью определенного упорядочения их элементов. Сюда относятся календарное планирование промышленного производства, задачи теории сетевого планирования и управления (СПУ), тактические и логические задачи, проблемы построения систем связи и исследования процессов передачи информации, выбор оптимальных маршрутов и потоков в сетях, методы построения электрических сетей, задачи идентификации в органической химии и способы построения переключательных схем. Таким же являются большой круг экономических задач, проблемы выбора структуры социальных групп, игровые задачи и головоломки и т.д. Таким образом, область возможных применений теории графов очень широка. Комбинаторные методы нахождения нужного упорядочения объектов существенно отличаются от классических методов анализа поведения систем с помощью уравнений. Кроме языка теории графов задачи упорядочения объектов можно формулировать в терминах теории матриц с элементами ноль – один, или в терминах теории конечных множеств.
Однако с полным основанием можно сказать, что теория графов является одним из простейших и наиболее элегантных разделов современной математики с широкой областью применения. Имея в своей основе простейшие идеи и элементы: точки, соединенные линиями, теория графов строит из них богатое многообразие форм, наделяет эти формы интересными свойствами и в результате становится полезным инструментом при исследовании самых разнообразных систем. Кроме того, теория графов внесла большой вклад в разработку методов анализа широкого круга комбинаторных проблем.
Вместо понятия графа часто используется понятие «сеть». Это особенно относится к случаям, когда кроме основных чисто структурных соотношений в графе задаются некоторые количественные характеристики точек и линий, образующих граф. В качестве примера можно назвать электрические сети, сети выполнения работ в проектах, сети потоков. При этом ребрам сети ставятся в соответствие определенные количественные характеристики энергии, затрат и потока.
Данная книга рассчитана на преподавателей, работающих со студентами выпускных курсов и аспирантами первого года обучения по специальности математика, естественные и общественные науки, технические науки, экономика и исследование операций. Как показал опыт практической работы со студентами, книга дает достаточно широкое общее представление о теории графов и разнообразных сферах ее применения и стимулирует развитие творческой активности учащихся. Материал книги является развитием курса, читавшегося в течение нескольких лет аспирантам университета Джорджа Вашингтона и студентам некоторых зарубежных учебных заведений.
Нам кажется, что любой человек, который готовит себя к работе в области науки или техники, должен познакомиться хотя бы с основами теории графов, так как эта теория является фундаментальной по своей природе и имеет широкую область применения. Одна из целей настоящей книги состоит как раз в том, чтобы обеспечить такое знакомство. Книгу можно рассматривать как вводный курс в теорию графов, или как пособие для самостоятельной работы. В использованной литературе имеется много статей, посвященных разнообразным частным проблемам, но они, конечно, не являются исчерпывающими.
Материал книги преподносится в форме неформального обсуждения основных идей. Четкость обсуждения усиливается за счет их иллюстрации разнообразными приложениями. Мы надеемся, что такой способ изложения
позволит читателю соотнести основные понятия теории графов с его собственными задачами, а убедившись в важности этой теории, читатель захочет и сам участвовать в ее дальнейшем развитии.
Книга состоит из двух частей. В первой части, включающей главы 1-5, дается основной теоретический материал. В главе 1 приводятся основные определения, термины и символы, необходимые для описания и классификации неориентированных графов. Глава заканчивается большим списком широко известных книг по основной теме и связанным с ней вопросам. В конце книги приводится исчерпывающая библиография, составленная Муном и Мозером. Она показывает чрезвычайно широкий диапазон обсуждаемых вопросов. В главе 2 приводятся определения, понятия и символы, используемые при рассмотрении ориентированных или направленных графов. Глава 3 является продолжением развития основных понятий. Основное внимание в ней уделяется способам разбиения элементов графа и измерению расстояния на графах. В главе 4 рассматриваются свойства и характеристики важного класса плоских графов и обсуждается класс проблем, получивших название задачи раскраски. В последней, пятой* главе первой части помимо геометрических понятий для характеристики графов начинают использоваться алгебраические понятия. Обсуждается роль матриц при описании и структурном анализе графов.
Вторая часть книги состоит из глав 6 и 7. Она иллюстрирует приложение развитой теории к самым различным областям. В большой и разнообразной по материалу в главе 6 кратко рассматриваются вопросы использования теории графов в самых различных ситуациях. В главе 7 проводится графотеоретическое рассмотрение потоков в сетях при наличии ограничений. Обсуждаются общие методы максимизации потоков и минимизации стоимости. Проводится краткое обсуждение потоков в стохастических сетях ﻼ показана связь основных идей в этой области с теорией массового обслуживания.
Для успешной работы с книгой читатель должен быть знаком с основной терминологией теории множеств и с элементарными понятиями аппарата теории матриц и векторных пространств.
Интересный вывод позволяет сделать теорема 1.2, которая приведена в главе 1. Из нее следует, что любой граф, число вершин и ребер которого выражается континуумом, может быть представлен в трехмерном пространстве без самопересечений. Хотя переход к более высокой размерности может упростить описание потоков, однако при этом совершенно не обязательно будут становиться более богатыми аналитические результаты. Важность последнего наблюдения становится особенно очевидной, если учесть, что человека можно в общих чертах описывать с помощью потоков в его нервной системе (характеризующейся неограниченными возможностями, в том числе способностью к многомерной абстракции). Эти потоки человек использует для управления своим собственным организмом и установления связи с внешней средой. Представляется, что использование трехмерного пространства является весьма адекватным и экономичным при реализации модели человека в виде системы потоков.
Мы благодарны Д. Эдмондсу за большое число предложений и добавлений, которые он сделал, особенно в части главы 6, и доктору X.Тренту за полезные идеи и обсуждение различных вопросов, связанных с содержанием книги. Мы признательны также за полезные предложения, в частности по главе 6, и за помощь при подборе и написании материала доктору Д. Розенблату (§ 6.2), Ч. Маклину (§ 6.10), доктору К. Фею (§ 6.4), Дж. Бушке, С. Мидору (§ 6.22), У. Муррею (§ 6.28), П. Риану и Э. Стерну.
Роберт Басакер
Томас Саати