К. Берж Теория графов и её применения. Перевод с французского А. А. Зыкова Под редакцией И. А. Вайнштейна Издательство литературы Москва 1962 Скачать бесплатно
Книга К. Бержа— первая книга по теории графов на русском языке. Между тем в последние годы интерес к этой теории резко усилился как со стороны математиков, так и представителей самых различных прикладных дисциплин. Это объясняется тем, что методы теории графов успешно решают многочисленные задали теории электрических цепей, теории транспортных сетей, теории информации, кибернетики и др. В книге Бержа геория графов излагается последовательно, начиная с основ. Предполагается, что читатель обладает весьма скромными математическими познаниями, хотя и имеет некоторую математическую культуру. В текст включены многочисленные зачастую забавные примеры. Книга может быть использована для первоначального изучения теории графов. Математики-профессионалы также найдут в ней много интересного.
Название:
Размер: 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
Полезные ссылки по теории графов и смежным дисциплинам. Программы, курсовые, рефераты, книги в электронном виде:
Книги в бумажном виде. Дискретная математика в Интернет-магазине:
Название |
Автор |
Издательство |
Год |
Цена |
|
Фурасов |
Бином. Лаборатория знаний |
2009 |
153руб. |
|
Кузнецов |
Лань |
2009 |
543руб. |
|
Пономарев |
Горячая Линия-Телеком |
2009 |
380руб. |
|
Спирина |
Academia |
2009 |
514руб. |
|
Москинова |
Логос |
2007 |
275руб. |
|
Крылов |
Факториал Пресс |
2007 |
2414руб. |
|
Галушкина |
Айрис-пресс |
2008 |
88руб. |
|
Шапорев |
BHV |
2009 |
261руб. |
|
Тишин |
BHV |
2008 |
234руб. |
|
Окулов |
Бином. Лаборатория знаний |
2008 |
274руб. |
|
Плотников |
Новое знание (Минск) |
2008 |
232руб. |
|
Шевелев |
Лань |
2008 |
880руб. |
|
Плотников |
Новое знание (Москва) |
2005 |
146руб. |
|
Просветов |
БИНОМ |
2008 |
183руб. |
|
Баврин |
Высшая школа |
2007 |
290руб. |
|
Аляев |
Финансы и статистика |
2006 |
150руб. |
|
Макоха |
ФИЗМАТЛИТ |
2005 |
338руб. |
|
Редькин |
Лань |
2006 |
59руб. |
|
Белоусов |
Издательство МГТУ им.Н.Э.Баумана |
2006 |
252руб. |
Ключевые слова: теория графов, виды графов, скачать учебник бесплатно, скачать книгу бесплатно, учебное пособие, курс лекций, граф, графы, связность графов, ориентированный граф, деревья, связность графов, кратчайший остов, кратчайший путь, задача о кратчайшем пути, фундаментальные, эйлеровы и гамильтоновы циклы, циклы в графе |