URSS.ru Магазин научной книги
Обложка Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов Обложка Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов
Id: 316801
999 р.

Лекции по теории графов Изд. 5, испр.

2024. 408 с.
Белая офсетная бумага

Аннотация

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

Для студентов вузов, обучающихся по специальностям «Математика» и «Прикладная математика». (Подробнее)


Отзывы
top

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

Выписка из указа Президента Республики Беларусь
N 625 от 28 декабря 1998 г.
"О присуждении Государственных премий Республики Беларусь 1998 года"

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

Ю.И.Журавлев, академик РАН, Москва

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

О.Б.Лупанов, член-корреспондент РАН, Москва

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

И.В.Сергиенко, академик Академии наук Украины, Киев
Н.3.Шор, член-корреспондент Академии наук Украины, Киев

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

В.В.Чавчанидзе, академик Академии наук Грузии, Тбилиси

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

В.Т.Дементьев, доктор физ.-мат. наук, Новосибирск
А.В.Косточка, доктор физ.-мат. наук, Новосибирск

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

К.А.Рыбников, доктор физ.-мат. наук, Москва

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

Н.Н.Петров, доктор физ.-мат. наук, Санкт-Петербург
И.В.Романовский, доктор физ.-мат. наук, Санкт-Петербург

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

И.Н.Ляшенко, доктор физ.-мат. наук, профессор, Киев
А.Ф.Волошин, доктор техн. наук, профессор, Киев

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

Г.П.Егорычев, доктор физ.-мат. наук, Красноярск

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

В.Н.Шевченко, доктор физ.-мат. наук, Нижний Новгород

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

А.А.Колоколов, доктор физ.-мат. наук, Омск

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

К.Присакару, доктор физ.-мат. наук, Кишинев
С.Катранчук, доктор физ.-мат. наук, Кишинев

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

Ш.С.Смагулов, доктор физ.-мат. наук, Алматы

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

М.Клин, профессор, Израиль

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

X. Ю.Фосс, профессор, Дрезден, Германия

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

Э.Гирлих, профессор, Германия

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

Н.К.Сегал, руководитель проектов корпорации "Интел", США

Оглавление
top
Предисловие9
Введение13
Глава 1. Начальные понятия14
1.1. Определение графа14
1.2. Подграфы21
1.3. Операции над графами23
1.4. Цепи, циклы, компоненты26
1.5. Степени вершин графа30
1.6. Матрицы, ассоциированные с графом31
1.7. Регулярные графы36
1.8. Метрические характеристики графа38
1.9. Критерий двудольности графа41
1.10. Реберный граф42
1.11. Группа автоморфизмов графа47
1.12. «Почти все» графы52
Упражнения55
Глава 2. Деревья58
2.1. Определение дерева58
2.2. Матричная теорема Кирхгофа62
2.3. Остов минимального веса65
Упражнения68
Глава 3. Матроиды и трансверсали70
3.1. Азбука теории матроидов70
3.2. Двойственный матроид75
3.3. Примеры матроидов77
3.4. Изоморфизм матроидов79
3.5. Представление матроида81
3.6. Бинарные матроиды86
3.7. Трансверсали94
3.8. Жадный алгоритм100
3.9. Объединение и пересечение матроидов102
Упражнения108
Глава 4. Независимость и покрытия110
4.1. Независимые множества и покрытия110
4.2. Клика119
4.3. Проблемы клики, изоморфной вложимости и изоморфного подграфа123
4.4. Интерпретации независимых множеств125
4.5. Паросочетания129
4.6. Паросочетания в двудольном графе132
4.7. Двудольные графы и семейства подмножеств136
4.8. Паросочетания и покрытия138
Упражнения140
Глава 5. Связность141
5.1. Вершинная связность и реберная связность141
5.2. Двусвязные графы145
5.3. Теорема Менгера154
Упражнения157
Глава 6. Планарность158
6.1. Плоские и планарные графы158
6.2. Грани плоского графа. Формула Эйлера161
6.3. Плоские триангуляции166
6.4. Критерии планарности168
6.5. Двойственность и планарность178
6.6. Алгоритм укладки графа на плоскости184
6.7. Характеристики непланарных графов193
Упражнения197
Глава 7. Обходы201
7.1. Эйлеровы графы201
7.2. Гамильтоновы графы206
Упражнения217
Глава 8. Степенные последовательности219
8.1. Графическая последовательность220
8.2. Критерии графичности последовательности222
8.3. Реализация графической последовательности с максимальной связностью229
8.4. Гамильтонова реализация графической последовательности231
8.5. Расщепляемые графы233
8.6. Пороговые графы235
8.7. Пороговое разложение графа240
8.8. Степенное множество графа244
Упражнения246
Глава 9. Раскраски248
9.1. Правильная раскраска248
9.2. Оценки хроматического числа251
9.3. Хроматический полином258
9.4. Раскраска ребер262
9.5. Связь матроидных разложений графов с раскрасками266
9.6. Раскраска планарных графов268
9.7. Проблема четырех красок274
9.8. Другие подходы к раскраске графов278
9.9. Совершенные графы281
9.10. Триангулированные графы286
Упражнения291
Глава 10. Ориентированные графы293
10.1. Основные определения293
10.2. Полустепени исхода и полустепени захода297
10.3. Обходы300
10.4. Пути304
10.5. База и ядро307
Упражнения310
Глава 11. Гиперграфы312
11.1. Основные определения и свойства312
11.2. Независимые множества318
11.3. Раскраски320
11.4. Реализации гиперграфа324
Упражнения329
Глава 12. Алгоритмы332
12.1. Предварительные сведения332
12.2. Поиск в глубину338
12.3. Отыскание двусвязных компонент341
12.4. Минимальный остов349
12.5. Кратчайшие пути357
12.6. Наибольшие паросочетания и задача о назначениях368
12.7. Труднорешаемые задачи379
Упражнения387
Список литературы389
Именной указатель391
Предметный указатель394

Предисловие
top
Посвящается Дмитрию Алексеевичу СУПРУНЕНКО

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

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

В главе 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. В.Яблонскому за постоянную помощь, ценные советы и поддержку.


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