Часто бывает полезно и наглядно изображать некоторую ситуацию в виде рисунка, состоящего из точек (вершин), представляющих основные элементы ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такие рисунки известны под общим названием графов, и эта книга посвящена их изучению. Графы встречаются во многих областях под разными названиями: структуры в гражданском строительстве, сети в электротехнике, социограммы в СОЦИОЛОГИИ и экономике, молекулярные структуры в химии, дорожные карты , электрические или газовые распределительные сети и так далее.

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

Хотя вообще считается, что эффективность алгоритмов имеет самое важное значение, автор не сводит свою книгу к справочнику эффективных алгоритмов. Часто метод рассматривается и по той причине, ЧТО он тесно связан с только что введенными понятиями (или получен из них) и ему отдается предпочтение, хотя имеются и другие алгоритмы, столь же (или даже порой несколько более) эффективные.

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

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

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

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

В главе 4 задача о раскраске вершин рассматривается как особый случай задачи о покрывающих множествах, изучавшейся в предыдущей тлаве. Даны приложения задачи раскрашивания к составлению расписаний, размещению ресурсов, а также ее обобщения на задачу доставки.

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

В главе 7 рассматриваются задачи о деревьях, кратчайших остовах и задача Штейнера, а также приложения этих задач к проектированию электрических и газовых распреде ительных сетей,

В главе 8 разбираются задача поиска кратчайшей цепи между парами вершин и ее приложения к задачам выбора маршрута для максимизации пропускной способности или надежности, к специальному случаю сетей ПЕРТ и к анализу критических маршру-

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

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

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

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

Часть этой книги была написана при финансовой поддержке Научного исследовательского совета по вопросам математического программирования, которому я очень признателен за оказанное содействие. В подготовке издания этой книги мне помогли очень многие. Я особенно благодарен профессору Сэму Эйлону, руководителю Отдела научного управления Империал колледжа, Питеру Виоле, Джеффу Сэлби, Питеру Брукеру и Сэму Кормэну. Я также хочу поблагодарить профессора Дональда Кнута, прочитавшего первый вариант рукописи и указавшего на несколько ошибок. Я в долгу перед г-жой Маргарет Хаджел, взявшей на себя тяжелый труд ПО перепечатке рукописи. Я должен отметить неоценимую помощь своей жены, которая не только безропотно терпела мою постоянную работу над книгой по вечерам, но также помогала при чтении корректур.

Никое Кристофидес

Октябрь 1973 Лондон