От редактора перевода

Книга Басакера и Саати «Конечные графы и сети» рассчитана на лиц, занимающихся использованием тео­рии графов при решении различных задач в области тех­ники, экономики, социологии. Она содержит основные понятия теории графов, достаточно полный перечень научных результатов и описание методов решения раз­личных задач.

Для лучшего понимания'и усвоения материала в кни­ге приводится большое число примеров, а также имеются учебные упражнения.

Следует заметить, что книга в целом написана не вез­де ровно и наряду с элементарными сведениями приво­дятся данные, требующие от читателя солидной матема­тической подготовки.

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

В процессе перевода поддерживался контакт с авто­рами, что позволило уточнить ряд мест. Кроме того, ис­правлены имевшиеся в оригинале неточности и опе­чатки.

Несмотря на то, что с момента выхода книги на анг­лийском языке прошло относительно длительное время, можно надеяться, что ее русское издание окажется полез­ным для широкого круга лиц, занимающихся при­кладными математическими вопросами, инженеров и экономистов.

А. Тейман

Предисловие

Теория графов дает простой, доступный и мощный ■исгрумент построения моделей и решения задач рюрадочения объектов. В настоящее время суще- enrjper множество проблем, где требуется построить ■ееогорые сложные системы с помощью определенного ffmrwMTim ах элементов. Сюда относятся календарное ——цюиааае промышленного производства, задачи те* «риш сетевого планирования н управления (СПУ), такти- чвопк в «юпиесжне заjaпроблемы построения систем —¹— а ■Рследоагння процессов передачи информации, ■нйкд» тшыьёы маршрутов и потоков в сетях, методы ■встуэеааа з.т=:-;трнчесхнх сетей, задачи идентификации a oprisi!веской .химии и способы построения переключа- ч*лаы£ых схем. Таким же являются большой круг эконо- шгееежнд задач, проблемы выбора структуры социальных гдаш, вгровые задачи и головоломки и т. д. Таким обра­зок, область возможных применений теории графов очень ■ирока. Комбинаторные методы нахождения нужного упорядочения объектов существенно отлйчаются от клас­сических методов анализа поведения систем с помощью уравнений. Кроме языка теории графов задачи упорядо­чения объектов можно формулировать в терминах теории матриц с элементами ноль — один, или в терминах тео­рия конечных множеств.

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

становится полезным инструментом при исследовании са- Д1ых разнообразных систем. Кроме того, теория графов внесла большой вклад в разработку методов анализа ши­рокого круга комбинаторных проблем.

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

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

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

Материал книги преподносится в форме неформально­го обсуждения основных идей. Четкость обсуждения уси­ливается за счет их иллюстрации разнообразными при­ложениями. Мы надеемся, что такой способ изложения

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

Книга состоит из двух частей. В первой части, вклю­чающей главы 1-г-5, дается основной теоретический мате­риал. В гла'ве 1 приводятся осмевные определения, тер­мины и символы, необходимые для описания и класси­фикации неориентированных графов. Глава заканчивает­ся большим списком широко известных книг по основной теме и связанным с ней вопросам. В конце книги приво­дится исчерпывающая библиография, составленная Му­ном и Мозером. Она показывает чрезвычайно широкий анапазон обсуждаемых вопросов. В главе 2 приводятся определения, понятия и символы, используемые при рас­смотрении ориентированных или направленных графов. Глава 3 является продолжением развития основных поня­тий. Основное внимание в ней уделяется способам раз­биения элементов графа и измерению расстояния на гра­фах. В главе 4 рассматриваются свойства и характери­стики важного класса плоских графов и обсуждается класс проблем, получивших название задачи раскраски. В последней, пятой* главе первой части помимо геомет­рических понятий для характеристики графов начинают использоваться алгебраические понятия. Обсуждается роль матриц при описании и структурном анализе графов.

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

Для успешной работы с книгой читатель долже быть знаком с основной терминологией теории множеств и с элементарными понятиями аппарата теории матриц и векторных пространств.

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

Книга состоит из двух частей. В первой части, вклю­чающей главы 1 -г-5, дается основной теоретический мате­риал. В гла'ве 1 приводятся осйевные определения, тер­мины и символы, необходимые для описания и класси­фикации неориентированных графов. Глава заканчивает­ся большим списком широко известных книг по основной теме и связанным с ней вопросам. В конце книги приво­дится исчерпывающая библиография, составленная Му­ном и Мозером. Она показывает чрезвычайно широкий диапазон обсуждаемых вопросов. В главе 2 приводятся определения, понятия и символы, используемые при рас­смотрении ориентированных или направленных графов. Глава 3 является продолжением развития основных поня­тий. Основное внимание в ней уделяется способам раз­биения элементов графа и измерению расстояния на гра­фах. В главе- 4 рассматриваются свойства и характери­стики важного класса плоских графов и обсуждается класс проблем, получивших название задачи раскраски. В последней, пятой* главе первой части помимо геомет­рических понятий для характеристики графов начинают использоваться алгебраические понятия. Обсуждается {юль матриц при описании и структурном анализе графов.

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

Для успешной работы с книгой читатель долже б'ыть знаком с основной терминологией теории множеств и с элементарными понятиями аппарата теории матриц и векторных пространств.

Интересный вывод позволяет сделать теорема 1.2, которая приведена в главе 1. Из нее следует, что любой граф, число вершин и ребер которого выражается континуумом, может быть представлен в трехмерном про­странстве без самопересечений. Хотя переход к более вы­сокой размерности может упростить описание потоков, однако при этом совершенно не обязательно будут ста-i новиться более богатыми аналитические результаты. Важность последнего наблюдения становится особенно очевидной, если учесть, что человека можно в общих чертах описывать с помощью потоков в его нервной системе (характеризующейся неограниченными возмож­ностями, в том числе способностью к многомерной абст­ракции). Эти потоки человек использует для управления своим собственным организмом и установления связи с внешней средой. Представляется, что использование трехмерного пространства является весьма адекватным и экономичным при реализации модели человека в виде системы потоков.

Мы благодарны Д. Эдмондсу за большое число пред­ложений и добавлений, которые он сделал, особенно в части главы 6, и доктору X. Тренту за полезные идеи и обсуждение различных вопросов, связанных с содержа­нием книги. Мы признательны также за полезные пред­ложения, в частности по главе 6, и за помощь при под­боре и написании материала доктору Д. Розенблату (§ 6.2), Ч. Маклину (§ 6.10), доктору К. Фею (§ 6.4), Дж. Бушке, С. Мидору (§ 6.22), У. Муррею (§ 6.28), П. Риану и Э. Стерну.

Роберт Басакер Томас Саати