Название:

Размер: 4,11 Мб

Описание: К. Берж Теория графов и её применения. Перевод с французского А. А. Зыкова Под редакцией И. А. Вайнштейна Издательство литературы Москва 1962

Ссылка для скачивания файла:

 

 

 

ОГЛАВЛЕНИЕ
Введение ... . . . 5
Глава 1 Основные определения . . . 7
Множества и многозначные отображения 7
Граф Пути и контуры . . 11
Цепи и циклы .... . 14
Глава 2 Предварительное изучение квазиупорядоченности 17
Квазипорядок, определяемый графом 17
Индуктивный граф  базы . 19
Глава 3 Порядковая функция и функция Гранди для бесконечного графа 23
Общие соображения огноапельно бесконечных графов . 23
Порядковая функция . . 27
Функции Гранди 29
Операции над графами 30
Глава 4 Основные числа теории графов 34
Цикломатическое число 34
Хроматическое число ... 37
Число внутренней устойчивости 46
Число внешней устойчивости 48
Глава 5 Ядра графа . .... 53
Теоремы существования и единственности 53
Приложение к функциям 1 ранд и . 59
Глава б Игры на графе . 61
Игра Ним . , . . . . 61
Общее определение игры (с полной информацией) 67
Стратегии . . 69
Глава 7 Задача о кратчайшем пути
Процессы по этапам . 75
Некоторые обобщения . 78
Глава 8. Транспортные сети . 82
Задача о наибольшем потоке 82
Задача о наименьшем потоке ... . . 88
Задача о потоке, совместимом с множеством значений
Бесконечные транспортные сети .
Глава 9 Теорема о полустепенях 98
Полу степени исхота и захода 98
Глава 10 Паросочетание простого графа 104
Задача о наибольшем паросочетании 104
Дефицит простого графа 108
Венгерский алгоритм . 112
Обобщение на бесконечный случаи 114
Приложение к теории матриц . . 117
Глава 11 Факторы . 120
Гамильтоновы пути и гамильтоновы контуры 120
Нахождение частичного графа с заданными

Г л а в а 12 Центры графа 131
Центры 131
Радиус 132
Глава 13 Диаметр сильно связного графа . 135
Общие свойства сильно связных графов без петель 135
Диаметр 138
Глава 14 Матрица смежности графа 142
Применение обычных, матричных операции 142
Задачи на подсчет 144
Задача о лидере . . 147
Применение булевых операций 150
Глава 15 Матрицы инциденций 153
Вполне унимодулярные матрицы 153
Вполне улнмодулярные 158
Цикломатические матрицы . . 161
Глава 16. Деревья и прадеревья 165
Деревья 165
Аналитическое исследование 170
Прадеревья 173
Глава 17 Задача Эйлера 179
Эйлеровы циклы 179
Эйлеровы контуры 182
Глава 18. Паросочетание произвольного графа 185
Теория чередующихся цепей 185
Нахождение частичного графа с заданными степенями вершин 189
Совершенное паросочетание . . 195
Приложение к числу внутренней устойчивости 200
Глава 19. Фактороиды 204
Гамильтоновы циклы и фактороиды 204
Необходимое и достаточное условие существования факторов 211
Глава 20 Связность графа 215
Точки сочленения 215
Графы без сочленений 217
Несвязные графы . . . . 221
ОГЛАБЛЕНПЬ 319
Глава 21 Плоские графы 227
Основные свойства 227
Обобщение 238
Добавления 241
Обобщения теории игр 243
II О транспортных задачах 250
III 06 использовании, понятия потенциала а транспортных сетях ... . 261
IV. Нерешенные задачи и недоказанные предположения . 270
V. О некоторых основных принципах подсчета (Ж Риге) 275
V/ Дополнения к русскому переводу (А А Зыков и Г Я. Кожухин) ...... 289
Литература 293

 

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Абелево слово 282
Абсолютное равновесие 70
Активный игрок 67
Алгоритм 50
— нахождения кратчайшего дерева 167
- пути 78, 79
— наибольшего паросочетания (венгерский алгоритм) 112
потока 85, 86, 292
— совместимого множества 192
— — наименьшего внешне устойчивого множества 51
— — — потока 89
— — потока, производящего наибольшую работу 258
— — — совместимого с интервалом
значений 95
пути выхода из лабиринта 76
базы независимых циклов 
— непосредственного выявления эйлерова цикла 181
— построения наибольшего паросочетания 114
— — наименьшей опоры 114
Антисимметрический граф 14
Антиузел 135
База векторного пространства 
— графа 19
Бержа—Нормана—Рэибина теорема 190
Бернштейна теорема 115
Бесконечная грань плоского графа 228
— транспортная сеть 96
Бесконечный граф 23, 24
Бинэ — Коши формула 170
Бистохастическая матрица 118
Бихроматический граф 
Благоприятная (оптимальная) стратегия 72
Брэттона гипотеза 140
Булево сложение
— умножение 152
Бюджет транспортной сети 255
Вектор цикла 35
Векторное подпространство З
Величина потока 82
— рассечения 126
Венгерский алгоритм 12
Верхняя грань 19
— структура 19
Вершина (точка) графа 12
Вес разбиения 279
Ветвь 135
Вещественное трехмерное пространство 9
Висячая вершина 165
Внешне устойчивое множество 48
Внутренне устойчивое множество 4S
Вполне индуктивный граф 20
— унимодулярная матрица 153
— упорядоченное множество 27
Вход 98
- транспортной сети 2
Выигрыш игрока 68, 244
Выход 93
— транспортной сети 82
Гамильтонов путь 120
— контур 120
— цикл 204
Генеалогическое (родословное) дерево 11
Географическая карта 38
Гипотеза Брэттона 140
— четырех красок 234, 236
Гракди функция 29
Граничные вершины дуги 12
Грань 227
Граф (определение)  12
— антисимметрический 14
— без контуров 
— _- сочленений 217
— бесконечный 23
— бихроматический 39
— вполне индуктивный 20 
Граф, двойственный данному 236, 239
- индуктивный 20
— конечный 23
— локально конечный 23 
- минимально связный 135
— однородный 198
— плоский 38 227, 238
— полный 14
— прогрессивно конечный 23
— — ограниченный 23
— простой 51, 88, 104
— псевдосимметрический 82
— регрессивно конечный 24
— — ограниченный 24
— связный 15
сильно связный 14
— симметрический 14
структурный 19
— типологический 227
— тотальный 18
— транзитивный 18
— частичный 12
— ай-плоский 76
— I -конечный 22
— Г~' конечный 22
— I -ограниченный 22
— fc-связный 223
— р-хроматический 
— S топологический 236
Группа подстановок 276
Двоичная запись числа 31
Двойственная строчка 99
Двойственный граф 236, 239
Декартово произведение 
Дерево 165
Дефицит простого графа 108
Диаметр графа 138
Динамические программы 79
— сети 83
Дирихле задача 262
Дирихле—Неймана задача 262
Длина дуги графа 78
— пути графа 13
— ребра графа 166
Дополнительная матрица 142
Дуга (графа) 12
Емкость графа 47
Задача Куаина 193
— Купманез 266
- о бомбардировке путей сообщения 222
Задача о волке, козе и капусте 76
о воспитанниках и воспитанницах
— — кёнигсбергских мостах
— книгах 123
— копе Аттилы 221
котловане и насыпи 251
— — лидере 147
— — назначении лиц 104
— — нахождении наименьшего покрытая 192, 193
— — прогулке молодых девушек
- пяти ферзях 49
— — пятнадцати девушках 44
— — разбиении прямоугольника
квадраты 262
— — распределение товаров по транспортной сети 252
— — складе 253
— — трех городах и трех источниках снабжения 227. 230
урезанной шахматной доске 144
— — ходе шахматного коня 122
часовых 49
— — шести красных дисках 49
— об информационной емкости множества сигналов 46
— — оптимальном назначении лиц 252
— — экскурсии 100
Замкнутая поверхность 238
Замкнутое кругосветное путешестние 120
Заходящая (в вершину в множество) дуга 13
— (в множество вершин) цепь 187
Игра 61, 67, 243 
в бридж 245
— Ним 61, 68
порядка р 64
— с полной информацией 67, 245
— — совершенной информацией 245
Игрок 67
Избыток 261
Изолированная вершина (точка) 98
Индекс положения игры 243
Инцидентность 13
Исходящая (из вершины из множества) дуга 13
Квазипорядок 17
— определенный графом 17
Кенига—Оре теорема 111
Кёнига теорема о бихроматических графах 39
Кёнига—Холла теорема 104 108
Класс эквивалентности 9
Классы транзитивности 276 277
Клика 44
Код 46
Комбинированная стратегия 246
Композиция отображений 10
Компонента связности 
Конец дуги 12
Конечная грань плоского графа 228
Конечный граф 23
Контур 13
Край, грани 227
Куна—Бёрча теорема 24Ь
Кусок графа 220, 231
— — внешний 232
— — внутренний 232
Лабиринт 75
Лапласа формула 170
Латинские квадраты 107
Лемма Цорна 20
- Эррера 199
Линейная конфигурация 170
Линейно зависимые некторы 36
— независимые векторы 35
Линейные программы 41, 81 84 190
Мажоранта 17
Максимальный элемент 20
Матрица инциденций  153
— ребер 153
-- смежности р графа 112
Менгера теорема 217
Минимально связный граф И5
Минимальный кусок 220
— элемент 20
Минор  18
Многочленный коэффициент 2
Множество 7
— изоляции 2
— информации 243
— сочленения 221
Моноид 174
Мультиграф 34
Наибольший элемент множеств 18
Наименьший элемент множества 18
Напоминание 246
Насыщенная дуга 86
Начало графа 186
— дуги 12
Недостижимая вершина 186 !95
Независимые циклы 35
Незамкнутное кругосветное путешествие 121
Ненасыщенная вершина 112 190 194
Неприводимая вершина 66
Несравнимые вершины 109
Нижняя грань 19
— структура 19
Нормальная форма игры 245
Обобщенная сумма матриц 150
Обобщенное произведение матриц 150
— сложение чисел 150
— умножение чисел 150
Образ 10
Обратное отображение 10
Объединение 8
Однородный граф 198
Ожидание выигрыша 214 216
Опора 200, 268
— оптимальная 2
— простого графа 109
Ориентируемая поверхность 238
Основной вероятностный закон (в игре) 243
Отклонение 1
Отклоненность 11
Отношение порядка 13
Отображение многозначное 10
— однозначное 10
Ощипывание графа 220
Паросочетанне произвольного 194
— простого графа 301
Пассивный игрок 67
Перемещение 101
Пересечение 8
Перешеек. 207
Периферийная точка 131
Перифероидпая точка 216
Петерсена—Галлаи теорема 188
Петерсена—Эрреота теорема 209
Петля 13
Планирование неполных блоков 89
Плоский граф 38, 227
— — топологический 227 238
Поверхность 238
Погоня 69
Подграф 12
Под игр а 68
Подмножество 7
Подстановка 275
— единичная 275
Поединок 72
Покрытие графа 88, 192
Простое паросочетание 
Полный граф 14
— поток 8
Положение игры 7, 243
Полустепень захода вершины 98
— исхода вершины 98
Понтрягика—Куратовского теорема 23
Порядковая функция графа 28
Порядковое (трансфинишное) число 27
Порядок 18
— вершины графа 28
Поток 82
— совместимый с убытками 261
— множеством значении 89
Потенциальная функция графа 262
Потребность вершины множества 90
Правило Тарри 77
— игры 67, 243
Предшествующая вершина 17
Проводимость дуги 262
Прогрессивно конечный граф 23
— ограниченный граф 23
Произведение графов 30, 46
Пропускная способность дуги 82
разреза 85
Простая цепь 15
Простой граф 51 88 101
— путь 13
— цикл 1
Пустое множество 7
Путь (в графе) 13
Работа потока 255
Равновесие (и игре) 70 214
Радиус графа 32
— -— ненаправленный («фадиоид»)
Радо теорема 25
Разбиение (множества) 9
— в смысле теории чисел 27
Размерность отображения 282
— разбиения 279
Разность потенциалов 261
Разрез (транспортной сети) 5
Рассечение графа 12G
Расстояние 131
— между вершин 215
Ребро графа 14
— мулы игр а фа 34
Регрессивно-конечный граф 24
Регрессивно ограниченный граф 24
Регулярность отношен ил 27Ь
— подстановки 276
Результат игры 72
Рейни проблема 18
Ричардсона теорема 56
Розеткя 135
Родословнoe (генеалогическое) дерево 11
Род поверхности 249
Связней граф 15
Сеть коммуникации 21S
Сигналы 4Ь
Сила игрока 149
— — итерированная порядка р 148
Сильно связный граф Н
Сильные вершины 136, 195
— дуги J12
- ребра 186,207
Симметрическая группа 277
Симметрический граф 14
Симплекс-метод 42, 85
Слабые вершины 186, 195
— дуги 112
— ребра 186, 189 207
Следующая вершина 17
Смежные вершины 13
— грани 227 228
— дуги 12
Смеша гита я вершина 186 195
Совершенная информация 245
Совершенное паросочетание 194
Совершенный прямоугольник 262
Совместимость множества ребер с
данной функцией 189
Сопротивление дуги 262
Сопряженная экиивалентность 279
Сопряженное отображение 281
Составная цепь
Составной путь 13
— цикл 15
Сохранное отображен е 47
Социо граммы 147
Способность бюджета 256
Старшинство 14
Степень вершины 180
— отображения 281
Стратегии 69, 244
Строго предшествующая вершина 17
— следующая першина 17
Структурное отношение порядка 19
Структурный граф 19
Стягивание множества вершин 135
Сvmmа графов 30
— порядка р игр Ним 64
Схема информации 183
— коммуникации 14
Теорема  Бержа о бесконечных транспортных сетях 115
— наибольшем внутренне устойчивом множестве 201
— Бернштейна 115
— Биркгофа —фон Неймана 119
— Бэблера 206
— Гейла 92
— Гофмана 93
— Дирака 124
— Жордана (о центроидах грфа) 216
— Кенига 112
— — о бихроматическнх графах 39
— гамильтоновом путе 123
— — — последовательностях 24
— Кенига—Ope 111
— Кёнига—Холла 104, 108
— Куна—Бёрча 246
— Менгера 217
— фон Неймана—Неша 246
— о полустепенях 98
— Перрона—Фробениуса 149, 150
— Петерсена 206
— Петсрсена—Галл аи 188
— Петерсена—Эррера 209
— Понтрлгйна—Куратовского
— Пуанкаре 160
— Радо 25
— Ричардсона 56
— Руа 135
— Татта 213
— о совершенном паросочетании 198
— Татта—Бержа 197
— Татта—Ботта 175
— Таусски 265
— Тэта 238
— Уитни 224
— Форда—Фалкерсона 87
— Хеллера 156
— Хеллера—-Томпкинса—Гейла 153
Тип отображения 281
— слова 282
Топологический граф 227 238
Тотальный граф 18
— квазипорпдок 18
Точка 7
— (вершина) графа 12
Точка простого сочленения 215
— сочленения 215
— равновесия (в игре) 244
Транзитивность 17
Транзитивный граф 18
Транспонированная матрица 142
Транспортная задача 250
— сеть 82
Турнирная диагрлмма 222
Удаленность вершины 215
Узел 135
Уитни теорема 224
Фактор графа 124
Фактор множество 276
Фактороид 204
Фан Тан (простая игра Ним) 63
Форда—Фалкерсона теорема 
Функция предпочтения 67, 243
Характеристическая функция множества 55
Xоcce диаграмма 18
Ход (в игре) 67, 243
Хроматический класс графа 38
Хроматическое число графе] 38
Центр графа 131
Центроид 216
Цепь 15
Цермело—фон
Цикл графа 15
— подстановки 276
Циклическая группа 277
Циклический индекс 2Й0
Цикломатическая матрица
матрица инцидетшй) 162
Цикломатическое число 34
теорема 70
вторая
Частичная игра 68
Частичный граф 12
— подграф 12
Чередующаяся цепь 185
Число внешней устойчивости 49
— внутренней устойчивости 43
— связности 225
Шахматы 
Эйлера формула 228
Эйлерова цепь 179
Эйлеров цикл 179
— контур 182
Эквивалентность 9
Эквивалентные 17
Элемент множества 7
Элементарное произведение 146
Элементарный контур 13
— путь 13
— цикл 15
матриц
Эффективное предпочтение
Ядро графа 53
ab плоский граф 1Ь
1-конечный граф 22
-конечный граф 22
-ограниченный граф 22
rf-сумма 31
— трансфинитных чисел 32
р-граф SB
р-хроматический граф 37
h-связный граф 223
S топологический граф 238
2 граф, 3-граф 34

 

 

 

Книги в бумажном виде. Дискретная математика в Интернет-магазине:

 

Ключевые слова: теория графов, виды графов, скачать учебник бесплатно, скачать книгу бесплатно, учебное пособие, курс лекций, граф, графы, связность графов, ориентированный граф, деревья, связность графов, кратчайший остов, кратчайший путь, задача о кратчайшем пути, фундаментальные, эйлеровы и гамильтоновы циклы, циклы в графе