Предисловие редактора перевода

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

Еще в период становления теории графов в ней возникало немало таких задач, решение которых предполагало построение некоторых алгоритмов (достаточно вспомнить, например, задачу о кёнигсбергских мостах и особенно задачу Гамильтона об обходе вершин додекаэдра). При этом, как правило, не накладывалось никаких ограничений на сложность алгоритмов, а лишь рассматривался вопрос их существования. Внедрение вычислительной техники поставило и перед всей математикой, и перед теорией графов проблему нахождения не произвольных алгоритмов, позволяющих решать те или иные классы задач, а таких алгоритмов, которые допускали бы практическую реализацию с использованием современных вычислительных устройств. Так возникла проблема практической разрешимости задач: найти эффективный или хотя бы достаточно простой в практически важных случаях алгоритм решения задачи. Классификация таких алгоритмов и методов их построения не может быть исчерпывающей. Однако всякое последовательное, систематическое изложение наиболее ярких и ценных алгоритмов, в частности алгоритмов «на графах», и приемов их получения является полезным и даже необходимым для прикладников. В этой связи можно упомянуть книги Ху [1], Корбута и Финкелыптейна [2], Цоя и Цхая [3].

В предлагаемой вниманию читателя книге предпринята весьма удачная попытка познакомить тех, кто интересуется прикладной теорией графов, с важными и перспективными алгоритмическими методами теории графов. Книга имеет ярко выраженный прикладной характер. Автор особо выделяет в ней вычислительные и алгоритмические аспекты теории графов. «Чистой» теории

графов в книге мало. Особый интерес представляют главы, посвященные размещению центров и медиан (гл. 5 и 6), задаче коммивояжера и паросочетаниям

Автор использовал терминологию Бержа [4]. Мы сочли благоразумным в ряде мест пользоваться терминологией Харари [5].

[1] Ху Т., Целочисленное программирование и потоки в сетях, М., «Мир», 1974.

[2] Корбут А. А. и Финкелыптейн Ю. Ю., Дискретное программирование, М., «Наука», 1969.

[3] Цой С. и Цхай С. М., Прикладная теория графов, Алма-Ата, «Наука», 1971.

[4] Берж К., Теория графов и ее применения, М., ИЛ, 1962. [5] Харари Ф., Теория графов, М., «Мир», 1973.

Г. Гаврилов

1978 г.

Предисловие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(кликните для просмотра скана)