Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов Изд. стереотип.

---

Президент Республики Беларусь, рассмотрев материалы, представленные Комитетом по Государственным премиям Республики Беларусь, постановляет: присудить Государственную премию Республики Беларусь за учебники: Емеличеву Владимиру Алексеевичу, Мельникову Олегу Исидоровичу, Сарванову Владимиру Ивановичу, Тышкевич Регине Иосифовне – за работу "Учебное пособие "Лекции по теории графов" для высших и средних специальных заведений".

N 625 от 28 декабря 1998 г.

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

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

Книга выгодно отличается от других тем, что она написана для начинающих и не требует наличия специальной подготовки; с другой стороны, книга дает достаточно адекватное представление о современном состоянии теории графов. Ряд представленных здесь результатов трудно найти в других книгах.

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

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

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

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

По охвату материала и, вместе с тем, лаконичности изложения и доступности использования различными категориями читателей (от школьников и студентов до преподавателей высшей школы и научных работников) пособие не имеет аналогов.

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

Книгу отличает удачное сочетание математической строгости с простотой и лаконичностью. Можно сказать, что, как учебник для студентов, книга практически не имеет недостатков.

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

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

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

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

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

Учебник является образцом полноты изложения. Он особенно важен студентам и лекторам, которые желают повысить свое образование.

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

---

Предисловие
Введение
Глава I.	НАЧАЛЬНЫЕ ПОНЯТИЯ
	§ 1.	Определение графа
	§ 2.	Подграфы
	§ 3.	Операции над графами
	§ 4.	Цепи, циклы, компоненты
	§ 5.	Степени вершин графа
	§ 6.	Матрицы, ассоциированные с графом
	§ 7.	Регулярные графы
	§ 8.	Метрические характеристики графа
	§ 9.	Критерий двудольности графа
	§ 10.	Реберный граф
	§ 11.	Группа автоморфизмов графа
	§ 12.	"Почти все" графы
	Упражнения
Глава II.	ДЕРЕВЬЯ
	§ 13.	Определение дерева
	§ 14.	Матричная теорема Кирхгофа
	§ 15.	Остов минимального веса
	Упражнения
Глава III.	МАТРОИДЫ И ТРАНСВЕРСАЛИ
	§ 16.	Азбука теории матроидов
	§ 17.	Двойственный матроид
	§ 18.	Примеры матроидов
	§ 19.	Изоморфизм матроидов
	§ 20.	Представление матроида
	§ 21.	Бинарные матроиды
	§ 22.	Трансверсали
	§ 23.	Жадный алгоритм
	§ 24.	Объединение и пересечение матроидов
	Упражнения
Глава IV.	НЕЗАВИСИМОСТЬ И ПОКРЫТИЯ
	§ 25.	Независимые множества и покрытия
	§ 26.	Клика
	§ 27.	Проблемы клики, изоморфной вложимости и изоморфного подграфа
	§ 28.	Интерпретации независимых множеств
	§ 29.	Паросочетания
	§ 30.	Паросочетания в двудольном графе
	§ 31.	Двудольные графы и семейства подмножеств
	§ 32.	Паросочетания и покрытия
	Упражнения
Глава V.	СВЯЗНОСТЬ
	§ 33.	Вершинная связность и реберная связность
	§ 34.	Двусвязные графы
	§ 35.	Теорема Менгера
	Упражнения
Глава VI.	ПЛАНАРНОСТЬ
	§ 36.	Плоские и планарные графы
	§ 37.	Грани плоского графа. Формула Эйлера
	§ 38.	Плоские триангуляции
	§ 39.	Критерии планарности
	§ 40.	Двойственность и планарность
	§ 41.	Алгоритм укладки графа на плоскости
	§ 42.	Характеристики непланарных графов
	Упражнения
Глава VII.	ОБХОДЫ
	§ 43.	Эйлеровы графы
	§ 44.	Гамильтоновы графы
	Упражнения
Глава VIII.	СТЕПЕННЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ
	§ 45.	Графическая последовательность
	§ 46.	Критерии графичности последовательности
	§ 47.	Реализация графической последовательности с максимальной связностью
	§ 48.	Гамильтонова реализация графической последовательности
	§ 49.	Расщепляемые графы
	§ 50.	Пороговые графы
	§ 51.	Пороговое разложение графа
	§ 52.	Степенное множество графа
	Упражнения
Глава IX.	РАСКРАСКИ
	§ 53.	Правильная раскраска
	§ 54.	Оценки хроматического числа
	§ 55.	Хроматический полином
	§ 56.	Раскраска ребер
	§ 57.	Связь матроидных разложений графов с раскрасками
	§ 58.	Раскраска планарных графов
	§ 59.	Проблема четырех красок
	§ 60.	Другие подходы к раскраске графов
	§ 61.	Совершенные графы
	§ 62.	Триангулированные графы
	Упражнения
Глава X.	ОРИЕНТИРОВАННЫЕ ГРАФЫ
	§ 63.	Основные определения
	§ 64.	Полустепени исхода и полустепени захода
	§ 65.	Обходы
	§ 66.	Пути
	§ 67.	База и ядро
	Упражнения
Глава XI.	ГИПЕРГРАФЫ
	§ 68.	Основные определения и свойства
	§ 69.	Независимые множества
	§ 70.	Раскраски
	§ 71.	Реализации гиперграфа
	Упражнения
Глава XII.	АЛГОРИТМЫ
	§ 72.	Предварительные сведения
	§ 73.	Поиск в глубину
	§ 74.	Отыскание двусвязных компонент
	§ 75.	Минимальный остов
	§ 76.	Кратчайшие пути
	§ 77.	Наибольшие паросочетания и задача о назначениях
	§ 78.	Труднорешаемые задачи
	Упражнения
СПИСОК ЛИТЕРАТУРЫ
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

---

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

Книга состоит из двенадцати глав.

В главе I даны основные понятия теории графов. Обсуждается гипотеза Келли–Улама о реконструируемости, вводятся регулярные, двудольные и реберные графы, изучается группа автоморфизмов графа. Глава заканчивается результатами, характеризующими свойства графов при большом числе вершин. Эти свойства отражают в некотором смысле типичный случай и потому формулируются в терминах "почти всех" графов.

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

Глава III содержит элементарное замкнутое изложение основ теории матроидов и трансверсалей, специально приспособленное к нуждам теории графов.

Глава IV касается понятий независимости и покрытия. При этом понятия вершинного и реберного покрытий в идейном плане объединены.

В главе V излагаются вопросы, связанные с вершинной и реберной связностью графа, которые имеют непосредственное отношение к надежности и живучести различных сетей. Особо выделены двусвязные графы. Приводятся новое краткое доказательство известной теоремы Менгера (1927 г.) о вершинном разделении графа, принадлежащее В.Маквайгу, и критерий Уитни (1932 г.) k-связности графа.

В главе VI приводятся критерии планарности графа Л.С.Понтрягина и К.Куратовского, X. Вагнера, С.Маклейна, X. Уитни, разбирается задача укладки графа на плоскости, даны некоторые характеристики неплапарности графа – род, толщина, число скрещиваний, искаженность.

Глава VII посвящена эйлеровым и гамильтоновым графам. Она открывается критерием существования эйлерова цикла в графе. Далее приводятся разнообразные достаточные условия гамильтоновости графа – результаты X. Уитни (1932 г.), У.Татта (1943 г.), Г.Дирака (1952 г.), О.Оре (1960 г.), В.Хватала (1972 г.) и др.

В главе VIII исследуются степенные последовательности графов, т.е. списки степеней их вершин. Приводятся два критерия графичности последовательности натуральных чисел – критерий Гавела–Хакими и критерий Эрдёша–Галлаи. Изучается процедура построения реализации графической последовательности с предписанными теоретико-графовыми свойствами. Исследуются классы графов, определяемые степенными последовательностями, – расщепляемые графы, пороговые графы. Последний класс графов связан с минимизацией числа линейных неравенств, задающих булеву функцию.

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

Глава X отведена ориентированным графам. Рассматриваются обходы и базы в ориентированном графе, детально исследуются пути.

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

Подобные задачи возникают при проектировании интегральных схем.

В главе XII вводится понятие полиномиального алгоритма (именно такие алгоритмы подразумеваются в гл.I–XI при употреблении словосочетания "эффективный алгоритм"). Глава содержит изложение двух алгоритмов анализа графов – поиска в глубину и поиска в ширину. Исследуются задачи нахождения кратчайших путей в графе, построения паросочетаний в двудольном графе, поиска кратчайшего остова во взвешенном графе. Дается введение в теорию NP-полноты.

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

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

За последние годы теория графов развилась в столь обширный самостоятельный раздел дискретной математики, что невозможно изложить все основные направления этого раздела в одной книге ограниченного объема. По этой причине очень трудно очертить круг вопросов, которые должны входить в учебное пособие для студентов-математиков. Очевидно, что в содержании настоящей книги отражены наши взгляды. Однако некоторые вопросы теории графов, привлекательные для нас, например, сети, транспортные сети, потоки в сетях и т.д., оказались за пределами этой книги, поскольку они традиционно входят в другие учебные курсы – такие как "Исследование операций", "Методы оптимизации", "Дискретная математика". Мы мало касались проблемы изоморфизма графов, которой, на наш взгляд, должна быть посвящена отдельная книга.

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

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

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

На различных стадиях работы над книгой мы пользовались советами и замечаниями, высказанными многими коллегами и нашими учениками. Среди них М.С.Гаращук, Г.М.Гутин, В.Э.Зверович, И.Э.Зверович, С.Г.Инджеян, А.Н.Исаченко, М.М.Ковалев, В.П.Козырев, Н.М.Корнеенко, А.Д.Коршунов, А.В.Косточка, А.П.Крачковский, А.Г.Левин, Л.С.Мельников, B. А.Перепелица, К.Ф.Присакару, В.Л.Тюрин, А.А.Черняк. Всем им мы выражаем искреннюю благодарность.

Мы от души благодарим рецензентов – коллективы кафедры математических методов исследования операций Воронежского государственного университета и кафедры теории исследования операций Ленинградского государственного университета; в частности, мы благодарны профессору Н.Н.Петрову и доценту И.Б.Руссману. Их детальная и благожелательная критика во многом способствовала улучшению первоначального текста книги. Мы благодарим также редактора книги А.Д.Вайнштейна, внесшего ряд усовершенствований в текст.

Мы особенно благодарны академику АН БССР Д.А.Супруненко и члену-корреспонденту АН СССР C. В.Яблонскому за постоянную помощь, ценные советы и поддержку.

---

Начало теории графов все единодушно относят к 1736 г., когда Л.Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашел критерий существования в графе специального маршрута (эйлерова цикла, как теперь его называют). Однако этот результат более ста лет оставался единственным результатом теории графов. Лишь в середине XIX века инженер-электрик Г.Кирхгоф разработал теорию деревьев для исследования электрических цепей, а математик А.Кэли в связи с описанием строения углеводородов решил перечислительные задачи для трех типов деревьев. К этому же периоду относится появление знаменитой проблемы четырех красок.

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

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

---

Слева направо: В.А.Емеличев, О.И.Мельников, Р.И.Тышкевич, В.И.Сарванов




Владимир Алексеевич ЕМЕЛИЧЕВ

Доктор физико-математических наук, профессор Белорусского государственного университета. Лауреат Государственной премии Республики Беларусь. Действительный член Нью-Йоркской академии наук, член редколлегии международных научно-теоретических журналов. Научные интересы: дискретная оптимизация, полиэдральная комбинаторика, теория графов, устойчивость и регуляризация многокритериальных дискретных задач. Автор и соавтор нескольких монографий.

Олег Исидорович МЕЛЬНИКОВ

Доктор педагогических наук, кандидат физико-математических наук, профессор Белорусского государственного университета. Лауреат Государственной премии Республики Беларусь. Научные интересы: теория графов, обучение дискретной математике в средней и высшей школе. Автор и соавтор нескольких монографий.

Владимир Иванович САРВАНОВ

Кандидат физико-математических наук, заведующий отделом Института математики Национальной академии наук. Лауреат Государственной премии Республики Беларусь. Научные интересы: теория графов, дискретная оптимизация, комбинаторная вычислительная геометрия. Автор и соавтор нескольких монографий.

Регина Иосифовна ТЫШКЕВИЧ

Доктор физико-математических наук, профессор Белорусского государственного университета. Лауреат Государственной премии Республики Беларусь. Заслуженный работник народного образования Беларуси. Основатель белорусской школы теории графов. Научные интересы: теория графов, комбинаторный анализ. Автор и соавтор нескольких монографий и учебных пособий.