Харари Ф. Теория графов.
Пер. с англ. Изд. 6, стереотип.

Оглавление

Предисловие

Прошло 30 лет после выпуска монографии Ф.Харари "Теория графов", но ее привлекательные качества нисколько не потускнели. Унификация терминологии, проведенной автором и широко распространенной благодаря этой книге, стала общепринятой. Преподавание теории графов с использованием книги Ф.Харари ведется во многих вузах нашей страны. За прошедшее время значительно расширилась сфера применения теории графов – при построении больших вычислительных систем и в программировании, в экономике и на транспорте, в генетике и биологии и т.д. Продолжается значительный рост публикаций, вышел в свет ряд учебных пособий и монографий, среди которых можно отметить книги А.А.Зыкова "Элементы теории графов" (М.: Наука, 1987) и В.А.Емеличева и др. "Лекции по теории графов" (М.: Наука, 1990).

Большое число задач, указанных в книге как нерешенные, нашли свое решение, и часть из них была решена многочисленными учениками Ф.Харари. Сам Ф.Харари, которому сейчас более 80 лет, плодотворно работает и публикуется до сих пор. Особенно значительные успехи за прошедшее время были получены по построению эффективных алгоритмов решения задач теории графов, среди которых нужно отметить алгоритмы построения максимального потока (см.: Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. М.: Наука, 1975). И это несмотря на то, что многие задачи теории графов – нахождение минимальных раскрасок, покрытий, максимальных полных подграфов, гамильтоновых циклов и др., – являются NP-полными, т.е. алгоритмически сложными (см.: Гэри М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи. М.: Мир, 1982). Недостаточную оснащенность книги Ф.Харари алгоритмами частично компенсирует книга Н.Кристофидеса "Теория графов. Алгоритмический подход" (М.: Мир, 1978). Обзор результатов по теории графов можно найти в работах: Козырев В.П. Теория графов // Итоги науки и техники. ВИНИТИ, сер. теор. вероятн., мат. стат. и теор. киберн. 1972. Т. 10. С.25–74; Козырев В.П., Юшманов С.В. Теория графов (алгоритмические, алгебраические и метрические проблемы) // Итоги науки и техники. ВИНИТИ, сер. теор. вероятн., мат. стат. и теор. киберн. 1985. Т. 23. С.68–117; Козырев В.П., Юшманов С.В. Представление графов и сетей (кодирование, размещения и укладки) // Итоги науки и техники. ВИНИТИ, сер. теор. вероятн., мат. стат. и теор. киберн. 1990. Т. 27. С.129–196.

11 ноября 2002 г.

Введение

Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. Эта теория тесно связана также со многими разделами математики, среди которых – теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ. Достоверно и то, что теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем, достойных внимания самых искушенных математиков.

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

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

Предлагаемые в конце каждой главы (кроме первой) упражнения существенно отличаются друг от друга по своей трудности. Номера тех упражнений, которые не являются простыми и не следуют непосредственно из приводимых ранее результатов, набраны жирным шрифтом. Особенно трудные упражнения кроме того помечены звездочкой. Для усвоения излагаемого в книге материала читателю рекомендуется ознакомиться с каждым упражнением. Многие из "более легких" упражнений могут показаться читателю очень трудными, если он не изучил материал соответствующих глав.

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

Считаю своим долгом выразить благодарность многим моим знакомым за их неоценимую помощь и советы в подготовке этой книги. Ловелл Байнеке и Гари Чартрэнд оказывали наибольшую помощь на протяжении многих лет!

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

За последние более чем двадцать лет, посвященных исследованиям в теории графов, я получал поддержку при публикации со стороны Научно-исследовательского управления Военно-воздушных сил США, Национальных институтов здоровья, Национального научного фонда, Управления научных разработок Военно-морского флота и фонда Рокфеллера. В течение этого времени я был рад воспользоваться гостеприимством не только Мичиганского университета, но также и других учебных заведений, которые я имел возможность посетить. Среди них – Институт повышения квалификации, Принстонский университет, Тавистокский институт социологии в Лондоне, Университетский колледж в Лондоне и Лондонская экономическая школа. Квалифицированно и быстро перепечатали рукопись Алиса Миллер и Анна Дженн из Научно-исследовательского центра групповой динамики. Наконец, я особенно благодарен издательству Аддисон-Уэсли за проявленное терпение в ожидании этой рукописи в течение всех десяти лет с момента заключения контракта, а также за всестороннюю помощь в издании книги.

Об авторе