АННОТАЦИЯ
Книга К. Бержа — первая книга по теории графов на русском языке. Между тем в последние годы интерес к этой теории резко усилился как со стороны математиков, так и представителей самых различных прикладных дисциплин. Это объясняется тем, что методы теории графов успешно решают многочисленные задачи теории электрических цепей, теории транспортных сетей, теории информации, кибернетики и др.
В книге Бержа теория графов излагается последовательно, начиная с основ. Предполагается, что читатель обладает весьма скромными математическими познаниями, хотя и имеет некоторую математическую культуру. В текст включены многочисленные, зачастую забавные примеры. Книга может Сыть использована для первоначального изучения теории графов. Математики-профессионалы также найдут в ней много интересного.
ВВЕДЕНИЕ
Во многих случаях жизни старая привычка толкает нас рисовать на бумаге точки, изображающие людей, населенные пункты, химические вещества и т. д., и соединять эти точки линиями или стрелками, означающими некоторые отношения. Такие схемы встречаются всюду под разными названиями: социограммы (в психологии), симплексы (в топологии), электрические цепи (в физике), диаграммы организации (в экономике), сети коммуникаций, генеалогические деревья и т. д. Д. Кёниг, без сомнения первый, предложил называть такие схемы „графами" и систематически изучать их свойства.
Весьма примечательно, что в совершенно различных дисциплинах приходится использовать аналогичные теоремы; так, понятие „матрицы инциденций", введенное Кирхгофомгдля изучения электрических цепей, было привлечено А. Пуанкаре в топологию при создании его „analysis situs"; понятие „точки сочленения", с давних пор известное в социологии, впоследствии появилось в электронике; все примеры такого рода перечислить невозможно. Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной.
В действительности такие основные понятия, как „цепь", „путь", „центр", будучи определены абстрактно, остаются в то же время неразрывно связанными с графической реальностью и легко распознаются, когда схема начерчена. Вот почему теорию графов нельзя смешивать с алгебраической теорией отношений, имеющей другие задачи. В то же время современная комбинаторная топология, игнорирующая ориентацию ребер и почти не интересующаяся понятиями, не обобщаемыми на случай п измерений, до сих пор мало что внесла в теорию графов. Например, некоторые результаты, относящиеся к чередующимся цепям, не похожи ни на алгебраические, ни на топологические теоремы. ;
Излагая здесь теорию графов, мы ставим целью дать в руки читателю математическое орудие, приложимое как к наукам о поведении (теории информации, кибернетике, играм, транспортным сетям), так и к теории множеств, теории матриц и к другим чисто абстрактным дисциплинам.
ОГЛАВЛЕНИЕ
Введение ............................... 5
Глава 1. Основные определения................. 7
Множества и многозначные отображения............ 7
Граф. Пути и контуры..................... 11
Цепи и циклы......................... 14
Глава 2. Предварительное изучение квазиупорядоченности ... 17
Квазипорядок, определяемый графом.............. 17
Индуктивный граф и базы................... 19
Г л а в а 3. Порядковая функция и функция Гранди для бесконечного графа.......:............... 23
Общие соображения относительно бесконечных графов..... 23
Порядковая функция...................... 27
Функции Гранди........................ 29
Операции над графами..................... 30
Глава 4. Основные числа теории графов............ 34
Цикломатическое число..................... 34
Хроматическое число...................... 37
i Число внутренней устойчивости ................. 43
Число внешней устойчивости.................. 48
Глава 5. Ядра графа....................... 53
Теоремы существования и единственности............ 53
: Приложение к функциям Гранди................ 59
i Г л а в а 6. Игры на графе..................... 61
Игра Ним........................... 61
Общее определение игры (с полной информацией)........ 67
Стратегии.......................... . 69
Глава 7. Задача о кратчайшем пути............... 75
Процессы по этапам...................... 75
Некоторые обобщения ,.................... 78
; Глава 8. Транспортные сети................... 82
Задача о наибольшем потоке . . •................ 82
Задача о наименьшем потоке.................. 88
Задача о потоке, совместимом с множеством значений...... 89
Бесконечные транспортные сети................. 96.
318 ОГЛАВЛЕНИЕ
Глава 9. Теорема о полустепенях ................ 98
Полустепени исхода и захода .................. 98
Глава 10. Паросочетание простого графа ............. 104
Задача о наибольшем паросочетании .............. 104
Дефицит простого графа .................... 108
Венгерский алгорифм ...................... 112
Обобщение на бесконечный случай ............... 114
Приложение к теории матриц .................. 117
Глава 11. Факторы ......................... 120
Гамильтоновы пути и гамильтоновы контуры .......... 120
Нахождение фактора .................... . . 124
Нахождение частичного графа с заданными полустепенями .... 128
Глава 12. Центры графа ............. . ........ 131
Центры .... ........................ 131
Радиус ............................. 132
Глава 13. Диаметр сильно связного графа ............ 135
Общие свойства сильно связных графов без петель ....... 135
Диаметр ............................ 138
Глава 14. Матрица смежности графа ............... 142
Применение обычных матричных операций ........... 142
Задачи на подсчет ....................... 144
Задача о лидере . ....................... 147
Применение булевых операций ................. 150
Глава 15. Матрицы инциденций .................. 153
Вполне унимодулярные матрицы ................ 153
Вполне унимодулярные системы ................. 158
Цикломатические матрицы ................... 161
Глава 16. Деревья и прадеревья .................. 1S5
Деревья ............................ 165
Аналитическое исследование .................. 170
Прадеревья ........................... 173
Глава 17. Задача Эйлера ...................... 179
Эйлеровы циклы ........................ 179
Эйлеровы контуры ....................... 182
Глава 18. Паросочетание произвольного графа .......... 186
Теория чередующихся цепей .................. 186
Нахождение частичного графа с заданными степенями вершин . . 189
Совершенное Паросочетание ................... 195
Приложение к числу внутренней устойчивости .......... 200
Глава 19. Фактороиды ....................... 204
Гамильтоновы циклы и фактороиды ............... 204
Необходимое и достаточное условие существования фактороида . 211
Глава 20. Связность графа Точки сочленения Графы без сочленений ft-связные графы
ОГЛАВЛЕНИЕ 319
Глава 21. Плоские графы..................... 227
Основные свойства....................... 227
Обобщение........................... 238
Добавления........................... 241
/. Об общей теории игр................. 243
//. О транспортных задачах............... 250
///; Об использовании понятия потенциала в транспортных сетях....................... 261
IV. Нерешенные задачи и недоказанные предположения . . 270
V. О некоторых основных принципах подсчета (Ж. Риге) 275
VI. Дополнения к русскому переводу (А. А. Зыков и
Г. И. Кожу хин.).................... 289
Литература ............................. 293
Теория графов и книга К. Бержа (послесловие к русскому переводу) ............................ 303
Указатель символов...................... 308
Именной указатель....................... 309
Предметный указатель..................... 311
Цена: 300руб.
