Сохранность книги — хорошая. ЦВЕТ ОБЛОЖКИ — ЗЕЛЁНЫЙ

GRAPH THEORY
by Frank Harary
PROFESSOR OF MATHEMATICS
UNIVERSITY OF MICHIGAN

ADDISON-WESLEY PUBLISHING COMPANY, 1969

Пер. с англ. В. П. Козырева

Формат 60x90 1/16. Бумага типографская №1

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

За последние годы тематика теории графов стала значительно разнообразней; резко увеличилось количество публикаций.

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

Предисловие редактора перевода	6
Введение	9

Глава 1. Открытие!	13
Задача о кёнигсбергских мостах	13
Электрические цепи	14
Химические изомеры	15
«Вокруг света»	16
Гипотеза четырёх красок	17
Теория графов в двадцатом веке	18

Глава 2. Графы	21
Типы графов	21
Маршруты и связность	26
Степени	27
Задача Рамсея	28
Экстремальные графы	30
Графы пересечений	33
Операции над графами	35
Упражнения	38

Глава 3. Блоки	41
Точки сочленения, мосты и блоки	41
Графы блоков и графы точек сочленения	45
Упражнения	46

Глава 4. Деревья	48
Описание деревьев	48
Центры и центроиды	51
Деревья блоков а точек сочленения	53
Независимые циклы и коциклы	54
Матроиды	57
Упражнения	59

Глава 5. Связность	60
Связность и рёберная связность	60
Графические варианты теоремы Менгера	64
Другие варианты теоремы Менгера	70
Упражнения	74

Глава 6. Разбиения	76
Упражнения	81

Глава 7. Обходы графов	83
Эйлеровы графы	83
Гамильтоновы графы	85
Упражнения	88

Глава 8. Рёберные графы	91
Некоторые свойства рёберных графов	91
Характеризация рёберных графов	94
Специальные рёберные графы	99
Рёберные графы и обходы	101
Тотальные графы	103
Упражнения	104

Глава 9. Факторизация	106
1-факторизация	106
2-факторизация	111
Древесность	113
Упражнения	116

Глава 10. Покрытия	117
Покрытия и независимость	117
Критические вершины и рёбра	120
Рёберное ядро	122
Упражнения	124

Глава 11. Планарность	126
Плоские и планарные графы	126
Внешнепланарпые графы	131
Теорема Понтрягина — Куратовского	133
Другие характеризации планарных графов	138
Род, толщина, крупность, число скрещиваний	141
Упражнения	148

Глава 12. Раскраски	151
Хроматическое число	152
Теорема о пяти красках	155
Гипотеза четырёх красок	156
Теорема Хивуда о раскраске карт	162
Однозначно раскрашиваемые графы	164
Критические графы	167
Гомоморфизмы	169
Хроматический многочлен	172
Упражнения	175

Глава 13. Матрицы	178
Матрица смежностей	178
Матрица инциденций	180
Матрица циклов	183
Обзор дополнительных свойств матроидов	186
Упражнения	187

Глава 14. Группы	189
Группа автоморфизмов графа	193
Операции на группах подстановок	194
Группа графа-композиции	195
Графы с данной группой	198
Симметрические графы	201
Графы с более сильной симметрией	204
Упражнения	206

Глава 15. Перечисления	209
Помеченные графы	209
Теорема перечисления Пойа	211
Перечисление графов	216
Перечисление деревьев	219
Теорема перечисления степенной группы	224
Решённые и нерешённые задачи перечисления графов	225
Упражнения	230

Глава 16. Орграфы	232
Орграфы и соединимость	232
Ориентированная двойственность и бесконтурные орграфы	234
Орграфы и матрицы	237
Обзор по проблеме восстановления турниров	244
Упражнения	244

Приложение I. Диаграммы графов	248
Приложение II. Диаграммы орграфов	260
Приложение III. Диаграммы деревьев	266

Список литературы и именной указатель	268
Указатель обозначений	291
Предметный указатель	293

Книги на ту же тему

Анализ и синтез линейных радиоэлектронных цепей с помощью графов: Аналоговые и цифровые фильтры, Остапенко А. Г., 1985
Теория графов, Оре О., 1968
Графы, сети и алгоритмы, Свами М., Тхуласираман К., 1984
Ориентированные графы и конечные автоматы, Мелихов А. Н., 1971
Теория просачивания для математиков, Кестен X., 1986
Кибернетическое моделирование. Некоторые приложения, Кемени Д. Д., Снелл Д. Л., 1972
Структуры данных, Берзтисс А. Т., 1974
Преобразования и перестановки, Калужнин Л. А., Сущанский В. И., 1979
Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
Структурное моделирование в CALS-технологиях, Павлов В. В., 2006
Информационно-вычислительные системы в машиностроении. CALS-технологии, Соломенцев Ю. М., Митрофанов В. Г., Павлов В. В., Рыбаков А. В., 2003
Структура данных и управление, Куцык Б. С., 1975
Введение в дискретную математику, Яблонский С. В., 1979
Экономико-математические методы. Вып. III: Экономико-математические модели народного хозяйства, 1966
Химические приложения топологии и теории графов, Кинг Р., ред., 1987

elapsed time 0.019 sec

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему