поговорим о ЛОНИИС

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » поговорим о ЛОНИИС » Теория графов » Книги по теории графов - оглавления


Книги по теории графов - оглавления

Сообщений 1 страница 17 из 17

1

Оглавление

Предисловие переводчика

Предисловие 12

Часть I. Точное совпадение строк: основная задача 19

1. Точное совпадение 25

1.1. Наивный метод 25
1.2. Препроцессная обработка 27
1.3. Основной препроцессинг образца   27
1.4. Основной препроцессинг за линейное время 29
1.5. Простейший алгоритм с линейным временем 31
1.6. Упражнения 33

2. Точное совпадение: классические методы 38

2.1. Введение 38
2.2. Алгоритм Бойера-Мура   39
2.3. Алгоритм Кнута-Морриса-Пратта   46
2.4. Поиск строк в реальном времени 51
2.5. Упражнения 53

3. Более глубокий взгляд 59

3.1. Метод Бойера-Мура с линейной оценкой времени ч 59
3.2. Линейная оценка Коула 64
3.3. Исходный препроцессинг по методу КМП 74
3.4. Точный поиск набора образцов 78
3.5. Три приложения точного множественного поиска 88
3.6. Поиск образца, заданного регулярным выражением 93
3.7. Упражнения 95

4. Получисленное сравнение строк 99

4.1. Что использовать: сравнения или арифметику? 99
4.2. Метод Shift-And 99
4.3. Задача о счете совпадений и FFT 103
4.4. “Дактилоскопические” методы 107
4.5. Упражнения 115

Чзсть II. Суффиксные деревья и их использование 117

5. Введение в суффиксные деревья 119

5.1. Краткая история 120
5.2. Основные определения 121
5.3. Побуждающий пример 122
5.4. Наивный алгоритм построения суффиксного дерева   124

6. Построение суффиксных деревьев за линейное время 126

6.1. Алгоритм Укконена 126
6.2. Алгоритм Вайнера 141
6.3. Алгоритм Мак-Крейга 150
6.4. Обобщенное суффиксное дерево для набора строк  151
6.5. Вопросы практической реализации 152
6.6. Упражнения 155

7. Первые приложения суффиксных деревьев 158

7.1. APL1; Точное совпадение строк 159
7.2. APL2: Суффиксные деревья и множественное точное совпадение 159
7.3. APL3: Задача о подстроке для базы образцов 160
7.4. APL4: Наибольшая общая подстрока двух строк 162
7.5. APL5; Распознание загрязнения ДНК 162
7.6. APL6: Общие подстроки более чем двух строк 164
7.7. APL7; Построение меньшего ориентированного графа    166
7.8. APL8: Обратная роль суффиксных деревьев 170
7.9. APL9: Эффективный по памяти алгоритм нахождения наибольшей общей
подстроки 174
7.10. APL10: Проверка совпадения суффикса с префиксом во всех парах 174
7.11. Введение в повторяющиеся структуры в молекулярных строках 177
7.12. APL11: Нахождение максимальных повторяющихся структур 183
7.13. APL12: Линеаризация циклической строки 189
7.14. APL13: Суффиксные массивы — большее сокращение памяти 190
7.15. APL14: Суффиксные деревья в геномных проектах 199
7.16. APL15: Подход Бойера-Мура к множественному совпадению 200
7.17. APL16: Сжатие данных по методу Зива-Лемпеля 208
7.18. APL17: Код минимальной длины для ДНК 212
7.19. Другие приложения 213
7.20. Упражнения 213

8. Общий наименьший предшественник 227

8.1. Введение 227
8.2. Предполагаемая модель машины 229
8.3. Полные двоичные деревья: очень простой случай 229
8.4. Как разрешать запросы об /ш в ^ 230
8.5. Первые шаги в отображении ЗГв 38 231
8.6. Отображение ЗГв ЗЬ 234
8.7. Препроцессинг ^"за линейное время 235
8.8. Ответы на запросы об lea за константное время 237
8.9. Двоичное дерево не очень нужно 240
8.10. Для пуристов: как избежать битовых операций 240
8.11. Упражнения 241

9. Дополнительные приложения суффиксных деревьев 245

9.1. Наибольшее общее продолжение: мост к неточному совпадению 245
9.2. Нахождение всех максимальных палиндромов за линейное время 247
9.3. Точное совпадение с джокерами 249
9.4. Задача о к несовпадениях 250
9.5. Приблизительные палиндромы и повторы 251
9.6. Более быстрые методы для тандемных повторов 252
9.7. Решение задачи о множественной общей подстроке за линейное время . . . 256
9.8. Упражнения 259

Часть III. Неточное сопоставление, выстраивание последовательностей
и динамическое программирование 261

10. Значение сравнения (под)последовательностей 265

11. Ядро методов редактирования строк и выстраивания 269

11.1. Введение 269
11.2. Редакционное расстояние между двумя строками 269
11.3 Вычисление расстояния динамическим программированием 272
11.4. Редакционные графы 278
11.5. Взвешенное редакционное расстояние 279
11.6. Сходство строк 281
11.7. Нахождение подстрок высокого сходства 286
11.8. Пропуски 292
11.9. Упражнения 303

12. Улучшение процедур выстраивания . 313

12.1. Вычисление выравниваний в линейной памяти 313
12.2. Ускорение для ограниченного числа различий 320
12.3. Методы исключения 332
12.4. Еще о суффиксных деревьях и гибридном ДП 343
12.5. Быстрый алгоритм для задачи les 351
12.6. Вогнутый вес пропусков 359
12.7. Метод “четырех русских” 369
12.8. Упражнения 375

13. Развитие основных задач 379

13.1. Параметрическое выравнивание последовательностей 379
13.2. Вычисление субоптимальных выравниваний 391
13.3. Сцепление различных локальных выравниваний 395
13.4. Упражнения 399

14. Сравнение многих строк — Святой Грааль 403

14.1. Зачем нужно множественное сравнение строк? 403
14.2. Три “крупномасштабных” применения 408
14.3. Представление семейств и суперсемейств 408
14.4. Выводы о структурах 414
14.5. Введение в вычисление множественных выравниваний строк 416
14.6. Выравнивание с целевой функцией типа суммы пар 417
14.7. Выравнивание с консенсусными целевыми функциями 426
14.8. Множественное выравнивание по (филогенетическому) дереву 430
14.9. Замечания о приближениях с ограниченной ошибкой 434
14.10. Обычные методы множественного выравнивания - 436
14.11. Упражнения 444

15. Базы данных для последовательностей 449

15.1. Истории успешного поиска в базах данных   450
15.2. Промышленность баз данных 453
15.3. Алгоритмические вопросы поиска данных 455
15.4. Реальный поиск в базе данных для последовательностей 456
15.5. FASTA . 457
15.6. BLAST   459
15.7. РАМ: первые главные матрицы подстановки аминокислот   462
15.8. PROSITE 466
15.9. BLOCKS и BLOSUM  467
15.10. Матрицы подстановки BLOSUM     .468
15.11. Дополнительные вопросы поиска в базе данных 469
15.12. Упражнения 474

Часть IV. Другие задачи: текущие, родственные и просто изящные 475

16. Карты, картирование, упорядочение и над строки 478

16.1. Взгляд на задачи картирования и секвенирования ДНК 478
16.2. Картирование и геномный проект 479
16.3. Физические и генетические карты 479
16.4. Физическое картирование 481
16.5. Физическое картирование: STS и библиотеки клонов 482
16.6. Физическое картирование: радиационно-гибридное 485
16.7. Физическое картирование: дактилограммы 490
16.8. Вычисление самой плотной раскладки 492
16.9. Физическое картирование: последние замечания 497
16.10. Введение в выравнивание карт 499
16.11. Крупномасштабная расшифровка и сборка последовательности 501
16.12. Направленная расшифровка 502
16.13. Нисходяще-восходящая расшифровка: картина, использующая YAC 503
16.14. Дробовая расшифровка ДНК 508
16.15. Сборка последовательности 508
16.16. Заключительные комментарии о нисходяще-восходящей расшифровке .  . .513
16.17. Задача о кратчайшей над строке 514
16.18. Расшифровка гибридизацией 527
16.19. Упражнения 534

17. Строки и эволюционные деревья 539

17.1. Ультраметрические деревья и расстояния 542
17.2. Деревья с аддитивными расстояниями 551
17.3. Бережливость: символьно-ориентированное эволюционное воссоздание . . . 554
17.4. Центральное место ультраметрической задачи 562
17.5. Максимальная бережливость, штейнеровы деревья 567
17.6. Снова филогенетическое выравнивание 569
17.7. Связи между множественным выравниванием и построением деревьев . . . 572
17.8. Упражнения 573

18. Три короткие темы 579

18.1. Сравнение ДНК с белком при смещениях рамки 579
18.2. Предсказание гена 582
18.3. Молекулярные вычисления: при помощи (а не ради) строк ДНК ...... . 585
18.4. Упражнения 591
19. Модели мутаций на геномном уровне 594
19.1. Введение 594
19.2. Инверсионные перестройки генома 596
19.3. Знакопеременные инверсии 601
19.4. Упражнения 602

Эпилог 604

Библиография 608

Толковый словарь 632

Англо-русский словарь терминов 644

Предметный указатель 646


ГАСФИЛД Дэн

Строки, деревья и последовательности в алгоритмах:
Информатика и вычислительная биология

Перевод с английского И. В. Романовского
Редактор О. М. Рощиненко
Издательство “Невский Диалект”
195220, Санкт-Петербург, Гражданский пр., 14. Лицензия ЛР № 065012 от 18.02.1997.
Издательство “БХВ-Петербург”
198005, Санкт-Петербург, Измайловский пр., 29. Лицензия ИД Na 02429 от 24.07.2000.
Подписано в печать 29.01.2003. Формат 70x100 1/16- Бумага газетная. Печать офсетная. Гарнитура Time Roman.
Уел. печ. л. 53,3.
Тираж 2000 экз. Заказ Na 728
Отпечатано С готовых диапозитивов в Академической типографии “Наука” РАН 199034, Санкт-Петербург, 9-я линия, 12.

0

2

Ласло Ловас, Майкл Д. Пламмер

Прикладные задачи теориии графов.
Теория паросочетаний в математике, физике, химии

ОГЛАВЛЕНИЕ   

Предисловие автора перевода  5

Предисловие 7

Основные термины  31

1. Паросочетание в двудольных графах  37
Введение 37
1.0. Теоремы Кёнига, Ф. Холла и Фробениуса 40
1.1. Алгоритм построения паросочетаний в двудольном графе:: венгерский метод 49
1.2. Дефицит, избыток и кое-что из теории матроидов 56
1.3. Некоторые следствия из теорем о паросочетаниях в двудольных графах   69

2 Теория потоков 84
2.0. Введение    84
2.1. Теорема о максимальном потоке и минимальном разре¬зе   : 86
2.2. Потоковые алгоритмы   90
2 3- Потоко-эквивалентные деревья 109
2.4. Применение теории потоков в теории паросочетаний .. 117
2.5. Паросочетания, потоки и меры.  125

3 Строение и размеры наибольших паросочетаний 134
3.0. Введение    134
3.1. Теорема Татта, лемма Галлаи и формула Бержа 135
3.2. Структурная теорема Галлаи —Эдмондса 147
3.3. Об исчислении барьеров. 158
3-4. Достаточные условия существования паросочетаний за-
даного размера 166

4 Двудольные графы с совершенными паросоче-
таниями
177
4.0. Введение 177
4.1. Элементарные двудольные графы и их колосковая структура ‘ 178
4.2. Минимальные элементарные двудольные графы 184
4.3. Разложение на элементарные двудольные графы 196

5 Общие графы с совершенными парасочетаниями 202
5.0. Введение   202
5.1. Элементарные графы: элементарные свойства 204
5-2. Каноническое разбиение V(G) 210
5.3. Насыщенные графы и купола 220
5.4. Колосковая структура 1-расширяемых графов 238
5.5. Еще кое-что о факторно-критических и бикритических графах 263

6 Некоторые задачи теории графов, связанные с паро-
сочетаниями
283
6.0. Введение 283
6.1. 2-паросочетания и 2-покрытия 283
6.2. 2-бикритические и регуляризуемые графы 288
6.3. Паросочетания, 2-паросочетания и свойство Кёнига ... 291
6.4. Гамильтоновы циклы и 2-паросочетания 301
6.5. Задача китайского почтальона 304
6.6. Оптимальные цепи, циклы, соединения и разрезы 319

7 Паросочетания и линейное программирование 333
7.0. Введение 333
7.1. Линейное программирование и паросочетания в двудоль¬ных графах 346
7.2. Паросочетания и дробные паросочетания 354
7.3. Политоп паросочетаний . 355
7.4. Хроматический индекс 368
7.5. Политопы дробных паросочетаний и полиэдры покры¬тий 375
7.6. Размерность политопа совершенных паросочетаний ... 376

8 Определители и паросочетания 392
8.0. Введение   392
8.1. Перманенты 395
8.2. Метод формальных переменных 401
8.3. Пфаффиан и число совершенных паросочетаний 405
8.4. Перечисление совершенных паросочетаний, базирующе¬еся на вероятностном подходе   418
8.5. Многочлены, перечисляющие паросочетания 422
8.6. Еще о числе совершенных паросочетаний 435
8.7. Два приложения в физических науках 440

9 Алгоритмы построения паросочетаний 447
9.0. Введение 447
9.1. Алгоритм Эдмондса 448
9.2. Взвешенные паросочетания 460
9.3. Алгоритм, основанный на теореме Галлаи — Эдмондса 468
9.4. Алгоритм линейного программирования для построения паросочетаний 472

10 Задача об f-факторе 477
10.0. Введение 477
10.1. Принципы сведения 479
10.2. Структурная теория /-факторов 482
10.3. Задача о наборах степеней вершин графов 501

11 Матроидные паросочетания 507
11.0. Введение   507
11.1. Формулировки задачи о матроидных паросочетаниях . 508
11.2. Основная теорема о полиматроидном паросочетаний .. 527
11.3. Паросочетания в специальных полиматроидах 536

12 Вершинные упаковки и покрытия 546
12.0- Введение 546
12.1. Критические графы 548
12.2. Политопы вершинных упаковок 562
12.3. Паросочетания в гиперграфах 573
12.4. Вершинные упаковки в графах, не содержащих клешней 579

Литература 593

Предметный указатель 637

Указатель обозначений

645
Ласло Ловас, Майкл Д. Пламмер

Прикладные задачи теориии графов.
Теория паросочетаний в математике, физике, химии

Заведующий редакцией академик В. И. Арнольд Ведущий редактор А. С. Попов Художник Н. В. Зотова Художественный редактор Н. В, Дубова Технический редактор Е. В. Денюкова Корректор Е. Н. Клитина
Оригинал-макет подготовлен В. Н. Цлаф в пакете TgX с использованием кириллических шрифтов, разработанных в редакции АИП издательства «Мир>>
Лицензия ЛР JV- 010174 от 20.05.97 г.
Подписано к печати 16.11.98. Формат 60 х 90/16. Бумага офсетная. Печать офсетная.
Объем 20,50 бум. л. Усл.-печ. л. 41;00. Уч.-изд. л. 42,10. Изд. № 1/8939. Тираж 5000 экз. (l-й завод 1000 экз.). Заказ 6606. С021 Издательство «Мир»
Государственного комитета Российской Федерации по печати 129820, ГСП, Москва, И-110, 1-й Рижский пер., 2
Отпечатано с готовых диапозитивов в Производственно-издательском комбинате ВИНИТИ 140010, г. Люберцы Московской обл., Октябрьский пр-т, 403.
Тел. (095) 554-21-86

0

3

Касьянов В. Н., Евстигнеев В. А.

Графы в программировании:
обработка, визуализация
и применение

УДК 681.3.06+519.6 ББК 32.81 К28
Касьянов В. Н., Евстигнеев В. А.

К28 Графы в программировании: обработка, визуализация
и применение. — СПб.; БХВ-Петербург, 2003. — 1104 с.: ил.
ISBN 5-94157-184-4
Книга содержит изложение фундаментальных основ современных компьютерных технологий, связанных с применением теории графов. Приведены основные модели, методы и алгоритмы прикладной теории графов. Рассмотрены задачи рисования графов и визуальной обработки графовых моделей. Описаны области приложения, такие как хранение и поиск ин-формации, трансляция и оптимизация программ, анализ, преобразование и распараллеливание программ, параллельная и распределенная обработка информации. В книге используется высокоуровневое описание алгоритмов, позволяющее понять алгоритм на содержательном уровне, оценить пригодность его для решения конкретной задачи и осуществить модификацию алгоритма, не снижая степень математической достоверности окончательного варианта программы.
Для научных работников, инженеров, преподавателей, аспирантов и студентов естественно-научных специальностей
УДК 681.3.06+519.6 ББК 32.81
Группа подготовки издания:
Главный редактор Екатерина Кондукова
Зам. главного редактора Анатолий Адаменко
Зав. редакцией Григорий Добин
Редактор Полина Столбова
Компьютерная верстка Ольги Сергиенко
Корректор Зинаида Дмитриева
Дизайн обложки Игоря Цырулышкова
Зав. производством Николай Тверских
Лицензия ИД № 02429 от 24.07.00. Подписано В печать 23.05.03.
Формат 70хЮ01Лб. Печать офсетная. Уел. печ л. 89.
Тираж 3000 ЭКЗ. Заказ № 202 "БХВ-Петербург", 198005, Санкт-Петербург, Измайловский пр., 29.
Гигиеническое заключение на продукцию, товар № 77.99.02.953.Д.001537.03.02 от 13.03.2002 г. выдано Департаментом ГСЭН Минздрава России.
Отпечатано с готовых диапозитивов в ФГУП ордена Трудового Красного Знамени "Техническая книга"
Министерства Российской Федерации по делам печати, телерадиовещания и средств массовых коммуникаций.
198005, Санкт-Петербург, Измайловский пр., 29.
ISBN
5-94157-184-4 Касьянов В. H., Евстигнеев В. А.. 2003
<0 Оформление, издательство "БХВ-Петербург", 2003

Содержание

Введение
15
[b]ЧАСТЬ I. ОБРАБОТКА И ВИЗУАЛИЗАЦИЯ ГРАФОВ[/b]
.....19
Глава 1. Графы и сети

     21
1.1, Неориентированные графы  21
1.1.1. Обыкновенные графы и их свойства 21
1.1.2. Деревья и их основные свойства 31
1.1.3. Хордальные графы и их классификация 34
1.1.4. Алгоритмы распознавания и раскраски 36
1.1.5. Кратчайшие цепи 40
1Д.6. Задача о минимальной связке 40
1.2. Орграфы и сети , 40
1.2.1. Орграфы   41
1.2.2. Кратчайшие пути  43
1.2.3. Генерация путей 46
1.2.4. Генерация контуров 48
1.2.5. Сети и задачи о потоках 50
1.2.6. Алгоритм Форда — Фалкерсона 52
1.2.7. Алгоритмы Диница и Карзанова 52
1.2.8. Изображение графов и сетей 56
Библиографический комментарий 57
Список литературы 58

Глава 2. Ориентированные деревья ..61

2.1, Ордеревья и их свойства 61
2.1.1. Корневые деревья 61
2.1.2. Бинарные деревья 66
2.1.3. Представление деревьев   67
2.1.4. Перечисление и подсчет деревьев 87
2.2. Обходы графов и деревьев в глубину и ширину 94
2.2.1. Разметки, нумерации, обходы, укладки 95
2.2.2. Базисные нумераций 96
2.2.3. Обходы в ширину и глубину    98
2.2.4. Остовный лес обхода в глубину и глубинное остовное дерево 99
2.2.5. Рекурсивный алгоритм обхода графа в глубину 100
2.2.6. Общий алгоритм обхода графа с запоминанием дуг 100
2.2.7. Общий алгоритм обхода графа с запоминанием его вершин 102
2.2.8. Алгоритм обхода графа в ширину с использованием внешней очереди 102
2.2.9. Алгоритм обхода графа в ширину с использованием внутренней очереди ..104
2.2.10. Алгоритм обхода графа в ширину без использования дополнительной памяти 105
2.2.11. Алгоритм обхода в ширину графа с циклическими списками дуг 107
2.2.12. Способы прохождения бинарных деревьев 109
2.2.13. Алгоритм обхода бинарного дерева в глубину с внешним стеком 110
2.2.14. Алгоритм обхода в глубину прошитого бинарного дерева 111
2.2.15. Замечания 112
2.2.16. Алгоритм обхода бинарного дерева в глубину без использования дополнительной памяти 113
2.2.17. Обход в глубину произвольных деревьев и лесов 115
2.2.18. Алгоритм обхода графа в глубину без использования дополнительной памяти 115
2.2.19. Алгоритм прямой нумерации вершин графа 117
2.2.20. Алгоритм базисных нумераций графа 118
2.2.21. Алгоритм обхода графа в глубину с двусторонним прохождением
дуг графа 119
2.2.22. Алгоритм обхода графа в глубину с двусторонним прохождением дуг
и распределенной реализацией стека 121
2.2.23. Алгоритм обхода графа в глубину с двусторонним прохождением дуг
и без использования дополнительной памяти 122
2.2.24. Алгоритм обхода в глубину графа, представленного в виде массива дуг,
с двусторонним прохождением дуг графа   125
2.3. Генерация деревьев 126
2.3.1. Алгоритм генерации упорядоченных деревьев 126
2.3.2. Алгоритм генерации бинарных деревьев 129
2.3.3. Алгоритм генерации бинарных деревьев заданной высоты . 131
2.3.4. Алгоритм генерации Парных деревьев 134
2.3.5. Алгоритм генерации корневых деревьев 135
2.3.6. Алгоритм генерации свободных деревьев 136
2.3.7. Генерация равновероятных деревьев   139
2.3.8. Алгоритм прямой генерации равновероятных упорядоченных
корневых деревьев 140
2.3.9. Алгоритм генерации по номеру равновероятных Парных деревьев 142
2.4. Каркасы   144
2.4.1. Задача об отыскании оптимального каркаса 144
2.4.2. Алгоритмы перечисления всех каркасов 160
2.4.3. Поиск каркасов с заданными свойствами 171
Библиографический комментарий 175
Список литературы 179

Глава 3. Бесконтурные графы 187

3.1. Основные свойства и алгоритмы 187
3.1.1. Основные свойства и подклассы 187
3.1.2. Топологическая сортировка 193
3.1.3. Кратчайшие пути 196
3.1.4. Критический путь 196
3.1.5. Путевое покрытие 197
3.2. Транзитивное замыкание и транзитивная редукция 198
3.2.1. Необходимые определения 198
3.2.2. Алгоритм Уоршалла 200
3.2.3. Общая форма алгоритма Уоршалла 200
3.2.4. Алгоритмы Горальчиковой-Коубека и Симона 202
3.2.5. Алгоритм Жомард-Мину ..205
3.2.6. Быстрый алгоритм слияния списков 206
3.2.7. Определение транзитивного замыкания и транзитивной редукции
при неполностью известной матрице смежности 208
3.2.8. Замыкание относительно множества вершин 210
3.3. Конгруэнтное замыкание отношения эквивалентности 211
3.3.1. Задача нахождения конгруэнтного замыкания .211
3.3.2. Быстрый алгоритм конгруэнтного замыкания 213
3.3.3. Ациклическое конгруэнтное замыкание 216
3.3.4. Уточнение алгоритма быстрого конгруэнтного замыкания 219
3.3.5. Случай единственной эквивалентности   222
3.3.6. Симметричное конгруэнтное замыкание 223
3.3.7. Унификация 224
3.3.8. Проверка эквивалентности выражений 224
3.3.9. Проверка свойства соединения без потерь 225
3.4. Нахождение ближайших предков 227
3.4.1. Постановка проблемы 227
3.4.2. Общий вид быстрого алгоритма для статических деревьев; 228
3.4.3. Сжатое дерево    230
3.4.4. Сбалансированное бинарное дерево 235
3.4.5. Быстрый алгоритм для задачи с соединением корней 238
3.4.6. Более быстрый алгоритм для задачи с соединением корней. 241
3.4.7. Заключительные замечания 243
3.5. Граф Герца  243
3.5.1. Бикомпоненты и граф Герца 243
3.5.2. Матричный алгоритм отыскания бикомпонент орграфа 244
3.5.3. Алгоритм Тарьяна отыскания бикомпонент 244
3.5.4. Пошаговая форма алгоритма Тарьяна 246
3.5.5. Алгоритм Фараджева 247
3.5.6. Алгоритм Касьянова 248
Библиографический комментарий 252
Список литературы 254

Глава 4. Сводимые и регуляризуемые графы   258

4.1. Класс сводимых графов 258
4.1.1. Уграф, фрагменты и подфрагменты 258
4.1.2. Альты, гамаки и интервалы 260
4.1.3. Отношения обязательного предшествования
и обязательной преемственности 262
4.1.4. F-лучи, F области и правильная нумерация   262
4.1.5. Фактор-уграфы     264
4.1.6. Интервальное представление уграфа,..., 265
4.1.7. Интервально-сводимые уграфы 267
4.1.8. Регуляризуемые уграфы     ,,,269
4.1.9. Аранжировка и аранжируемые графы   271
4.1.10. Разборные уграфы               272
4.1.11. Алгоритм проверки сводимости графа     273
4.1.12. Упрощенный вариант алгоритма.....       276
4.1.13. Порядок втягивания вершин             278
4.1.14. Преобразование несводимых графов        279
4.1.15. Преобразования расщепления 279
4.1.16. Стандартное преобразование 282
4.2. Разрушение контуров в сводимых графах        ..283
4.2.1. Постановка задачи          283
4.2.2. Необходимые определения       284
4.2.3. Потоковая сеть для G       .285
4.2.4. Определение мощности минимального множества разрывающих дуг . . .288
4.2.5. Нахождение минимального множества вершин, разрезающего циклы, 289
4.2.6. Приближенный алгоритм нахождения множества разрывающих дуг 291
4.2.7. Алгоритм Бергера — Шора          293
4.2.8. Алгоритм Шамира     ........295
4.3. Анализ циклической структуры и циклически сводимые графы.....  ..297
4.3.1. Понятие цикла в уграфе   298
4.3.2. Достоверные частотные отношения 298
4.3.3. Участки повторяемости   ,.... 299
4.3.4. Циклические участки графа   301
4.3.5. Циклически сводимые графы    304
4.3.6. Полные Z)-последовательности     ,306
4.3.7. Связь со сводимыми графами      308
4.3.8. Алгоритм Шпекенмейера для задачи FVS.       ..310
4.4. Перечисление путей ,       311
4.4.1. Сильные и слабые укладки   311
4.4.2. Построение укладок   313
4.4.3. Постановка задачи перечисления 314
4.4.4. Формальная постановка задачи 315
4.4.5. Алгоритмы перечисления путей 319
4.4.6. Алгоритм прямого потокового анализа 322
Библиографический комментарий  .329
Список литературы 331

Глава 5. Визуализация     335

5.1. Задача и методы визуализации 335
5.1.1. Рисование графов на плоскости 336
5.1.2. Ортогональные изображения 340
5.1.3. Использование физических аналогий 345
5.1.4. Трехмерные представления 346
5.1.5. Изображение помеченных графов 349
5.2. Планарные графы и их изображения 351
5.2.1. Планарные графы и их свойства 352
5.2.2. Рисование деревьев 357
5.2.3. Рисование последовательно-параллельных графов 363
5.2.4. Рисование бесконтурных графов 366
5.2.5. Переход к планарному графу 371
5.2.6. Выпуклые представления 374
5.2.7. Методы, основанные на канонических упорядочениях...: 377
5.3. Поуровневое рисование ориентированных графов   379
5.3.1. Общая схема поуровневого подхода 380
5.3.2. Распределение вершин по уровням    384
5.3.3. Определение порядка вершин на уровне 388
5.3.4. Определение координат вершин на уровне     394
5.3.5. Предварительные преобразования графа 396
5.4. Иерархические графы и графовые модели 398
5.4.1. Иерархические графы 399
5.4.2. Изображения иерархических графов 403
5.4.3. Иерархические графовые модели 407
5.4.4. Использование инвариантных свойств для задания семантики модели 408
5.4.5. Трансформационный подход к заданию семантики графовой модели 410
5.5. Системы визуализации графов и графовых моделей 412
5.5.1. Вопросы визуализации и визуальной обработки 412
5.5.2. Системы визуализации и графовые редакторы 415
5.5.3. Графовые библиотеки 430
5.5.4. Система HIGRES 436
Библиографический комментарий 440
Список литературы 442

ЧАСТЬ II. ПРИМЕНЕНИЕ ГРАФОВ И ГРАФ-МОДЕЛЕЙ   449

Глава 6 Информационные деревья.,, 451
6.1. Одномерные структуры данных .452
6.1.1. Деревья сортировки     452
6.1.2. Д5Л-деревья   * 454
6.1.3. Балансированные по весу деревья (55-деревья)..... 455
6.1.4. Выровненные деревья 459
6.1.5. 1-2-братские деревья 461
6.1.6. 2-3-деревья,„„ 468
6.1.7. Кучи    475
6.1.8. 5-деревья   481
6.1.9. Другие страничные деревья 492
6.2. Многомерные структуры данных - 498
6.2.1. Многомерное дерево сортировки     498
6.2.2. Многомерные 5-деревья 505
6.2.3. Деревья множественных атрибутов     515
6.2.4. Парадигмы для МАТ-структур   320
Библиографический комментарий 523
Список литературы 525

Глава 7. Синтаксические деревья  527

7.1. Синтаксис языка и задача фазы анализа  527
7.1.1. Синтаксис языка, лексемы, понятия и атрибуты...   527
7.1.2. Схема процесса трансляции,,.,     532
7.1.3. Лексический, синтаксический и контекстный анализ   533
7.2. Порождающие грамматики     535
7.2.1, Цепочки и языки,        535
7.2.2, Грамматики составляющих       536
7.2.3. Контекстно-свободные языки       „ 538
7.2.4. Эквивалентные преобразования грамматик .     540
7.3. Лексический анализ ,.          543
7.3.1. Распознаватели..,,             543
7.3.2. Функции лексического анализа 546
7.3.3. Реализация лексического анализатора 548
7.4. Синтаксический анализ 549
7.4.1. Стратегии разбора     549
7.4.2. Автоматы с магазинной памятью       550
7.4.3. Нисходящий АЯ7-распознаватель     553
7.4.4. Л-грамматики и /./.-распознаватель.... 556
7.4.5. Восходящий Л/Я-распознаватель   557
7.4.6. Грамматики предшествования   559
7.4.7. Горизонтальный разбор 561
7.4.8. Алгоритм Эрли     564
7.4.9. /.Д-грамматики.....          565
7.4.10. ГД-анализатор     566
7.4.11. Обработка синтаксических ошибок 568
7.5. Перевод и конструкторы анализаторов     571
7.5.1. Понятие перевода, СУ-схемы и преобразователя 571
7.5.2. Конструктор лексических анализаторов 573
7.5.3. Конструкторы синтаксических анализаторов 575
7.5.4. Конструктор Л-преобразователя     576
7.5.5. Конструктор LR-преобразователя     579
7.5.6. Использование конструкторов 581
Библиографический комментарий 582
Список литературы 582

Глава 8. Контекстный анализ 584

8.1. Задача контекстного анализа    584
8.1.1. Атрибуты абстрактной программы 584
8.1.2. Области видимости и идентификация 586
8.1.3. Атрибутная индукция     587
8.2. Атрибутные грамматики 590
8.2.1. Определение атрибутных грамматик 590
8.2.2. Пример атрибутной грамматики 592
8.2.3. Атрибутное вычисление 593
8.3. Конструирование абстрактных синтаксических представлений 597
8.3.1. Абстрактное синтаксическое дерево и построение дерева выражения 597
8.3.2. Дэги выражений 600
8.3.3. Метод нумерации для конструирования вершин в дэге 601
8.4. Основные подклассы атрибутных грамматик и вычислений 603
8.4.1. Чисто синтезированные грамматики 603
8.4.2. /-упорядоченные грамматики 605
8.4.3. Сильно ациклические грамматики  606
8.4.4. Вычислители для грамматик общего вида 608
8.4.5. Восходящее вычисление для ^-атрибутных грамматик 609
8.5. T-атрибутные грамматики     610
8.5.1. Порядок обхода в глубину и L-атрибутные грамматики 610
8.5.2. Трансляционные схемы 611
8.5.3. Удаление левой рекурсии из трансляционной схемы 612
8.5.4. Конструирование предсказывающего транслятора 615
8.5.5. Удаление встроенных действий из трансляционных схем 617
8.5.6. Наследуемые атрибуты на стеке разбора 618
8.5.7. Восходящий разбор и трансляция с синтезируемыми атрибутами 620
8.5.8. Замена наследуемых атрибутов синтезированными 621
8.5.9. Пример атрибутной грамматики, трудной для обработки .622
8.5.10. Рекурсивные вычислители и обходы слева направо 622
8.5.11. Другие обходы рекурсивных вычислителей 624
8.6, Распределение памяти под атрибуты 625
8.6.1. Вводные замечания   626
8.6.2. Распределение памяти под атрибуты во время трансляции 627
8.6.3. Удаление копирований .....629
8.6.4. Распределение памяти во время конструирования транслятора 630
8 6.5. Пример генерации промежуточного представления 630
8.6.6. Неперекрывающиеся времена существования 632
Библиографический комментарий 634
Список литературы . 636
Глава 9. Кодогенерации 640
9.1. Задача кодогенерации и объектная машина 640
9.1.1. Задача кодогенерации 641
9.1.2. Вход кодогенератора 643
9.1.3. Трехадресные представления   644
9.1.4. Объектные программы 646
9.1.5. Управление памятью 647
91.6. Выбор команд 648
9.1.7. Распределение регистров 649
9.1.8. Выбор порядка вычисления 650
9.1.9. Архитектура объектной машины 650
9.1.10. Стоимость команды     652
9.2. Управление памятью периода исполнения 653
9.2.1. Вводные замечания     653
9.2.2. Статическое распределение   -654
9.2.3. Стековое распределение   655
9.2.4. Адресация периода исполнения для имен 658
9.3. Линейные участки и управляющие графы 659
9.3.1. Линейные участки и их выделение 659
9.3.2. Преобразования на линейных участках 662
9-3.3. Информация о последующем использовании 663
9.3.4. Управляющие графы и представление лучей      665
9-4, Простой кодогенератор      667
9.4.1. Вводные замечания            667
9.4.2. Дескрипторы регистров и адресов   668
9.4.3. Алгоритм кодогенерации 668
9.4.4. Функция нахождения места размещения 669
9.4.5. Генерация кода для операторов других типов 671
9.4.6. Условные операторы 672
9.5. Распределение и присваивание регистров 673
9.5.1. Глобальное распределение регистров 673
9.5.2. Счетчики использований   674
9.5.3. Присваивание регистров для внешних циклов 677
9.5.4. Распределение регистров путем раскраски графа 677
9.6. Представление лучей дэгами и генерация кода по дэгу 678
9.6.1. Представление линейных участков в виде дэгов 679
9.6.2. Конструирование дэга луча 679
9.6.3. Применение дэгов 682
9.6.4. Массивы, указатели и вызовы функций 684
9.6.5. Генерация кода по дэгу 686
9.6.6. Задача переупорядочения   686
9.6.7. Эвристическое упорядочение для дэгов 687
9.6.8. Оптимальное упорядочение деревьев   689
9.6.9. Алгоритм разметки 689
9.6.10. Генерация кода по помеченному дереву 691
9.6.11. Многорегистровые операции... 693
9.6.12. Алгебраические свойства 694
9.6.13. Общие подвыражения 695
9.7. Алгоритм кодогенерации, основанный
на динамическом программировании 695
9.7.1. Класс регистровых машин 696
9.7.2. Принцип динамического программирования
и непрерывное вычисление 696
9.7.3. Непрерывное вычисление 697
9.7.4. Алгоритм динамического программирования 697
9.8. Покадровая.оптимизация   700
9.8.1. Понятие покадровой оптимизации 700
9.8.2. Избыточные загрузки и запоминания 701
9.8.3. Недостижимый код 701
9.8.4. Оптимизации потока управления 702
9.8.5. Алгебраические упрощения 703
9.8.6. Понижение силы операции....    703
9.8.7. Использование машинных идиом 704
9.9. Генерация кодогенераторов 704
9.9.1. Генерация кода и переписывание деревьев   704
9.9.2. Поиск по образцу при разборе     710
9.9.3. Процедуры семантической проверки   711
9.9.4. Покрывающие деревья 712
9.9.5. Система BEG   713
9.10. Генерация оптимального кода для стековых машин 715
9.10.1. Стековая машина ц корневые деревья 715
9.10.2. Стековые вычисления 718
9.10.3. Коммутативные операции .-. 720
9.10.4. Ассоциативные коммутативные операции   721
Содержание
11
Библиографический комментарий 725
Список литературы 728
.
Глава 10. Потоковый анализ программ   735

10.1. Анализ потока управления 736
10.1.1. Представление множеств исполнений  736
10.1.2. Структуризация 740
10.1.3. Нахождение свойств операторов и переходов 741
10.1.4. Выбор порядка обработки операторов 742
10.2. Гамачное представление уграфов 747
10.2.1. Иерархия вложенных альтов 747
10.2.2. Нумерации К и L 750
10.2.3. Алгоритм АГ-нумерации 751
10.2.4. Алгоритм А-нумерации 752
10.2.5. Свойства нумераций К и L 753
10.2.6. Алгоритм выделения гамаков 754
10.3. Отношения обязательного предшествования
и обязательной преемственности 755
10.3.1. Отношение доминирования и их свойства 756
10.3.2. Семидоминаторы 757
10.3.3. Алгоритм Ленгауэра — Тарьяна 759
10.3.4. Реализация операций LINK и EVAL 763
10.3.5. Общий вид алгоритма Ленгауэра — Тарьяна 765
10.3.6. Микродеревья и их использование 767
10.3.7. Линейный алгоритм Бухбаума — Каплана — Роджерс 769
10.3.8. Инкрементальное вычисление доминаторных деревьев 772
10.3.9. Алгоритм нахождения доминаторов в сводимом уграфе 777
10.4. Структурная сложность программ 778
10.4.1. Понятие сложности программы 778
10.4.2. Цикломатйческая мера Мак-Кейба 779
10.4.3. Другие меры сложности, основанные на уграфе 782
10.4.4. Декомпозиция уграфов 786
10.5. Потоковый анализ программ 791
10.5.1. Задача анализа потока данных •. 791
10.5.2. Метод разметки    794
10.5.3. Примеры задач анализа свойств состояний 796
10.5.4. Алгоритм нахождения стационарной разметки 798
10.5.5. Факторизация...   801
10.5.6. Свойства схем анализа свойств состояний 803
Библиографический комментарий 812
Список литературы 814

Глава 11. Преобразование программ    818

11.1. Унификация и системы переписывания термов 818
11.1.1. Задача унификации 819
11.1.2. Унификация как решение множества уравнений 820
11.1.3. Мультиуравнения и алгоритмы их решения 822
11.1.4. Улучшение алгоритма унификации при обработке неунифицируемых данных    827
11.1.5. Алгоритм проверки унифицируемости, основанный
на представлении термов дэгами .     829
11.1.6. Линейный алгоритм унификации Патерсона — Вегмана    831
11.1.7. Алгоритм Уэ 834
11.1.8. Сравнение алгоритмов унификации 836
11.1.9. Эквациональные спецификации..   .........838
11.1.10. Понятие системы переписывания термов   840
11.1.11. Свойство Черча — Россера, конфлюэнтность, нетеровость
и полнота системы переписывания термов 841
11.1.12. Локальная конфлюэнтность и критические пары   842
11.1.13. Построение полных СПТ для эквациональных теорий.   844
11.1.14. Методы доказательства нетеровости, основанные на упорядочении 848
11.1.15. Алгоритм Кнута — Бендикса ..850
11.2. Промежуточные представления программ...   853
11.2.1. Требования к промежуточному представлению 853
11.2.2. Граф зависимостей по данным 855
11.2.3. Зависимость по управлению   857
11.2.4. Граф программных зависимостей    860
11.2.5. Построение графа зависимостей 861
11.2.6. Иерархический граф заданий 865
11.2.7. Построение ИГЗ     867
11.3. Операторные модели программ 874
11.3.1. Семантические и формальные схемы программ   874
11.3.2. Класс крупноблочных схем программ 875
11.3.3. Важные подклассы и их свойства   880
11.3.4. Перераспределение памяти   883
11.3.5. Схемы с распределенной памятью 885
11.3.6. Схематизация программ 891
11.3.7. Схемы с косвенной адресацией 892
11.3.8. Корректные псевдораскраски   896
11.3.9. Модель аннотированных программ 898
11.3.10. Преобразования программ 900
Библиографический комментарий 902
Список литературы 907

Глава 12. Прочие граф-модели 914

12.1. Диаграммы бинарных решений 914
12.1.1. Упорядоченные диаграммы бинарных решений
и логические фрагменты 915
12.1.2. Конструирование и манипуляция 922
12.1.3. Представление математических объектов 929
12.1.4. Другие применения .....933
12.2. Частично упорядоченные множества 943
12.2.1. Основные определения 943
12.2.2. Параметры чу-множеств 946
12.2.3. Частично упорядоченные множества и графы   947
12.2.4. Решетки, подрешетки и полурешетки 949
12.2.5. Теорема о неподвижной точке 956
Содержание

12.2.6. Кодирование частичных порядков 957
12.2.7. Прозрачные частичные порядки и их применения 962
12.2.8. Чу-множества и модели параллельных программ и процессов
12.3, Сети Петри 971
12.3.1. События и условия 972
12.3.2. Определение сети Петри 973
12.3.3. Основные свойства сетей Петри
12.3.4. Ограниченность и безопасность сети   
12.3.5. Классы языков сетей Петри 981
12.3.6. Подклассы сетей Петри
12.3.7. Обобщения сетей Петри 988
12.3:8. Регулярные сети
12.3.9. Иерархические сети
12.4, Графы адресуемых данных 998
12 4.1. Граф данных
12.4.2. Реализация графов данных
12.4.3. Относительная адресация
12 4.4. Вложения графов 1005
Библиографический комментарий     1007
Список литературы 1009

ЧАСТЬ III   ПРИЛОЖЕНИЯ

    1
Приложение 1. РАМ, ВУ-язык и список АР-полных задач

1.1. РАМ и понятие  NP полноты 1016
1.1.1. Равнодоступная адресная машина 1017
1.1.2. Вычислительная сложность РАМ-программ 1019
1.1.3. Свойства РАМ, связь РАМ с другими моделями вычислений 1020
1.1.4. Труднорешаемые и NP-полные задачи      1021
1.2. Язык высокого уровня 1023
1.2.1. Структуры данных      1024
1.2.2. Структуры действий  1027
1.2.3. Дополнительные средства  1030
1.3. Список NP-полных задач    1030
1.3.1. Покрытия и разбиения    1030       
1.3.2. Подграфы и изоморфизм 1032
1.3.3. Расположения, укладки и нумерации 1036
1.3.4. Остовные деревья  1038
1.3.5. Разрезы и связность   1041
1.3.6. Пути     1041       
1.3.7. Сети....    1042    .
1.3.8. Множества и разбиения      1046            
1.3.9. Хранение и поиск.      1049   
1.3.10. Программы и схемы      1053           
1.3.11. Автоматы и языки          1056
1.3.12. Логика ...     1058
1.3.13. Игры и головоломки  1059   
1.3.14. Алгебра и теория чисел 1062

1.3.15. Математическое программирование 1064
1.3.16. Теория расписаний            1066
1.3.17. Разные задачи............ . ...      1069
Библиографический комментарий      1070
Список литературы     1072

Приложение 2. Характеристики размещений графов........ 1074

2.1. Размер области размещения   1074
2.1.1. Деревья   1075
2.1.2. Планарные графы     1076
2.1.3. Графы общего вида 1077
2.2. Оценка величины углов... ... ...               1077
2.3. Число сгибов 1077
2.4. Связь разных характеристик 1078
2.4.1. Связь между размером и отношением сторон
при изображении деревьев..,      1078
2.4.2. Связь между размером области и величины углового разрешения
для планарных графов       1079
2.5. Вычислительная сложность        1079
2.5.1. Проверка планарности и вложения 1079
2.5.2. Прямолинейные и полилинейные изображения планарных графов.... 1080
2.5.3 Изображения графов с заданной степенью вершин 1080
2.5.4. Рисование деревьев     . 1081
Библиографический комментарий   1082
Список литературы 1082

Предметный указатель   1087

Отредактировано ABC (2017-07-05 16:07:42)

0

4

Харари Фрэнк

Теория графов

ББК 22.144 22.18 22.19
Харари Фрэнк
Теория графов
/ Пер. с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаври¬лова. Изд. 3-е, стереотипное. — М.: КомКнига, 2006. — 296 с.
ISBN 5-484-00457-8
В последнее время теория графов привлекает все более пристальное внимание специалистов различных областей знания. Наряду с традиционными применения¬ми ее в таких науках, как физика, электротехника, химия, она проникла и в науки, считавшиеся раньше далекими от нее, — экономику, социологию, лингвистику и др. Давно известны тесные контакты теории графов с топологией, теорией групп и теорией вероятностей. Особенно важная взаимосвязь существует между теорией графов и теоретической кибернетикой (особенно теорией автоматов, исследова¬нием операций, теорией кодирования, теорией игр). Широко используется теория графов при решении различных задач на вычислительных машинах.
Предлагаемая книга написана видным специалистом по дискретной матема¬тике. Несмотря на небольшой объем и конспективный характер изложения, книга достаточно полно освещает современное состояние теории графов. Она, безуслов¬но, будет полезна студентам университетов и технических вузов и, несомненно, заинтересует широкие круги научных работников, занимающихся приложениями дискретной математики.

Издательство «КомКнига*. 117312, г. Moci Подписано к печати 09.02.2006 г. Формат
Отпечатано в ООО «ЛЕНАНД». 117312, г.
.ва, пр-т 60-летия Октября, 9.
S0 х 90/16. Печ. л. 18,5. Зак. JVfe 436.
Москва, пр-т 60-летия Октября, д. 11 А, стр. 11.
ISBN 5—484—00457—8

ОГЛАВЛЕНИЕ

Я не люблю цитат» Скажи, что знаешь сам,

Р. Эмерсон


Предисловие 4

Введение . 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

0

5

УДК 519 ББК 22.176 Г67
Горшков А.Ф.
Г67 Метод замещений. - М.: КноРус, 2004. — 184 с.
ISBN 5-94761-049-3
Впервые в мировой научной литературе достаточно подробно описываются новые системы ограничений на степени вершин неориентированного графа - векторы топологии, рассматриваются особености метода замещений, которые позволяют ему конкурировать с  такими классическими методами как венгерский метод, метод ветвей и границ, динамическое программирование, метод штрафования вершин и др.
Приводятся алгоритмы решения оптимизационных и комбинаторных задач на графах из новых классов. В основе этих алгоритмов лежит принцип парных замещений. Книга дает достаточно полное представление о современных направлениях исследования теории графов.
Книга представляет интерес для научных работников, инженеров, занимающихся прикладными задачами, преподавателей, пирантов и студентов вузов.
УДК 5 ББК 22.1
ISBN 5-94761-049-3

СОДЕРЖАНИЕ

Предисловие 3

Часть I НЕМНОГО ТЕОРИИ

Глава 1. Введение        7
1.1. Графы. Типы графов 7
1.2. Связные графы и компоненты связности графа 8
1.3. Степени вершин графа 10
1.4. Матричные представления графов   10
1.6. Подграфы и суграфы  13
1.7. Задачи   13

Часть II ОСНОВЫ МЕТОДА ЗАМЕЩЕНИЙ

Глава 2. Ограничения на топологию исходных графов
и искомых суграфов 14
2.1. Векторы топологии      14
2.2. Векторы закрепленных степеней    14
2.3. Векторы допустимых степеней 16
2.4. Вектор запрещенных степеней 17
2.5. Вектор подвижных степеней 18
2.6. Сдвиг компонент векторов ...20
2.7. Задачи Л. 20

Глава 3 Основные виды замещений на графах  21
3.1. Принцип замещений 21
3.2. Пары реберных замещений    22
3.3. Принцип парных реберных замещений 24
3.4. Порфириан замещений   26
3.5. Дерево замещений 28
3.6. Дуговые замещения    32
3.7. Вершинные замещения  33
3.8. Задачи    39

Глава 4. Деформация и релаксация суграфов  40
4.1. Начальная деформация суграфа .40
4.2. Промежуточная деформация суграфа 42
4.3. Предварительная релаксация суграфа   43
4.4. Предварительная релаксация связности 51
4.5. Задачи    .......53

Глава 5. Задачи на неориентированных графах 55
5.1. Примеры оптимизационных задач на неориентированных графах     55
5.2. Венгерский метод и метод замещений   57
5.3. Метод ветвей и границ и метод замещений 58
5.4. Метод замещений и динамическое программирование .. 63
5.5. Метод штрафования вершин и метод замещений 64
5.6. Подходы к снижению трудоемкости решения задач методом замещений   ... 65
5.7. Алгоритм формирования дерева замещений при решении оптимизационных задач   68
5.8. Алгоритм решения оптимизационных задач (ОПТ) 69
5.9. Комбинаторные задачи на неориентированных графах. 69
5.10. Алгоритм КОМБ   70
5.11. Алгоритм формирования начального суграфа при решении комбинаторных задач (ФОРСУГ) 72
5.12. Задачи 73

Глава 6. Задачи на двудольных графах 75
6.1. Векторы топологии для двудольных графов  75
6.2. Теорема о соотношениях исходных параметров искомого суграфа   77
6.3. Применимость алгоритмов ОПТ и КОМБ при решении задач на двудольных графах 79
6.4. Задачи   81

Глава 7. Задачи на к-дольных графах   82
7.1. Основные термины, понятия и определения 82
7.2. Вторичные векторы топологии. Локальные
и глобальные векторы топологии   83
7.3. Соотношения глобальных и локальных векторов топологии к-дольных графов 85
7.4. Оптимизационные задачи на к-дольных графах. Функционал   86
7.5. Комбинаторные задачи на к-дольных графах 91
7.6. Задачи   92

Глава 8. Деревья  93
8.1. Задача о кратчайшем остовном дереве 93
8.2. Деревья Романовского 97
8.3. Деревья Штейнера на графах 99
8.4. Дерево Габова   . 101
8.5. Кратчайшие гамильтоновы цепи    102
8.6. Звездные суграфы 103
8.7. Лес  105
8.8. Задачи  106

Глава 9. Оптимальные циклы при наличии ограничений 107
9.1. Задача коммивояжера 107
9.2. Задача о К коммивояжерах  107
9.3. Кратчайшие эйлеровы циклы и задача
сельского почтальона с предписанными степенями вершин 108
9.4. Отыскание кратчайших эйлеровых циклов с системой ограничений типа «слоеный пирог»   110
9.5. Задача китайского почтальона 112
9.6. Задачи 113

Часть III ПРИЛОЖЕНИЯ МЕТОДА ЗАМЕЩЕНИЙ

Глава 10. Прикладные задачи, решаемые
методом замещений 114

10.1. Диофантовы модели молекул ДНК и РНК 114
10.2. Составим учебное расписание 120
10.3. Маркетинговая модель «Товар — реклама - рынок» .. 125
10.4. Как поддержать уровень ликвидности многофилиального банка   136
10.5. Простейшие модели изомеров и химических реакций
в органической химии    141
10.6. Решение шахматных этюдов 146
10.7. Распределение заказов по станкам с учетом потребностей сборочного участка 156
10.8. Задачи развозки грузов потребителям 161
10.9. Объединение электростанций в энергосистему  165
10.10. Настоящее и будущее метода замещений   168

Библиография  173


ООО «Издательство Гном и Д»
Ответственный за выпуск — А Казаков Оригинал-макет — Н. Залипаева
Издательство «КНОРУС»
129110, г. Москва, ул. Большая Переяславская, д. 46 Тел./факс: (095) 280-12-78, 280-06-71
E-mail: com.knorus.ru
Сдано в набор 20.12.04. Подписано в печать 00.00.04. Печать офсетная. Объем — 11,5 п. л. Формат 60x90/16. Тираж— 500 экз.
УДК 519.1 ББК 22.176 К60


||||||||||||||||||||||||||||||||||

К о л ч и н В. Ф. Случайные графы. — М.: ФИЗМАТЛИТ, 2002. — 256 с. — (Теория вероятностей и математическая статистика.) — ISBN  5-9221-0233-8.
Книга посвящена случайным графам, случайным подстановкам, систе-мам случайных линейных уравнений в конечных полях и уравнениям, содержащим неизвестную подстановку. Изложение отличается система-тическим использованием обобщенной схемы размещения, при котором многие комбинаторные задачи сводятся к задачам о суммах независимых случайных величин.
Для специалистов в области вероятностной комбинаторики и ее приме-нений, инженеров и студентов старших курсов вузов.
Библ. 167 назв.
© ФИЗМАТЛИТ, 2002 ISBN  5-9221-0233-8 | - . © В.Ф. Колчин, 2002

Оглавление

ПРЕДИСЛОВИЕ 5

ГЛАВА 1. ОБОБЩЕННАЯ СХЕМА РАЗМЕЩЕНИЯ И КОМПОНЕНТЫ
СЛУЧАЙНЫХ ГРАФОВ
1.1. Вероятностный подход к перечислительным задачам комбинаторики ...... 9
1.2. Обобщенная схема размещения 24
1.3. Связность графов и обобщенная схема размещения . . 33
1.4. Леса из некорневых деревьев 42
1.5. Размеры деревьев в случайном лесе      -7 54
1.6. Максимальный размер деревьев в случайном лесе ... 62
1.7. Графы с одноцикловыми компонентами 73
1.8. Графы с компонентами двух типов   85
1.9. Замечания и литературные ссылки 103

Глава 2. ЭВОЛЮЦИЯ СЛУЧАЙНЫХ ГРАФОВ
2.1. Докритические графы 109
2.2. Критические графы 115
2.3. Случайные графы с независимыми ребрами 120
2.4. Неравновероятные графы 130
2.5. Замечания и литературные ссылки , 141

ГЛАВА 3. СИСТЕМЫ СЛУЧАЙНЫХ ЛИНЕЙНЫХ УРАВНЕНИЙ В GF(2)
3.1. Ранг матрицы и критические наборы 144
3.2. Матрицы с независимыми элементами 149
3.3. Ранг матрицы с малым числом единиц 157
3.4. Циклы и совместность систем случайных уравнений . . 167
3.5. Гиперциклы и совместность систем случайных уравнений 179
3.6. Замечания и литературные ссылки 188

ГЛАВА 4. СЛУЧАЙНЫЕ ПОДСТАНОВКИ
4.1. Случайные подстановки и обобщенная схема размещения 196
4.2. Число циклов 198
4.3. Подстановки с ограничениями на длины циклов .... 208
4.4. Замечания и литературные ссылки 212

Глава 5. Уравнения, СОДЕРЖАЩИЕ неизвестную ПОДСТАНОВКУ
5.1. Уравнения второй степени ; 221
5.2. Уравнения простой степени 228
5.3. Уравнения составной степени 238
5.4. Замечания и литературные ссылки .    243

Список литературы 245

Предметный указатель 254
Научное издание
КОЛЧИН Валентин Федорович СЛУЧАЙНЫЕ ГРАФЫ
Серия «Теория вероятностей и математическая статистика»

Оригинал-макет автора
ЛР № 071930 от 06.07.1999. Подписано в печать 08.11.2000.
Формат 60x90/16. Бумага офсетная. Печать офсетная. Уел. печ. л. 16. Уч.-изд. л. 16,5. Тираж 300 экз. Заказ № 119.
Издательская фирма «Физико-математическая литература» МАИК «Наука/Интерпериодика»
117864 Москва, Профсоюзная ул., 90
E-mil: fizmat@maik.ru
Отпечатано с готовых диапозитивов в ФГУ П «Московская типография № 6» Министерства РФ по делам печати, телерадиовещания и средств массовых коммуникаций 109088 Москва, Ж-88, Южнопортовая ул., 24
9 785922 102339
9785922102339

Отредактировано ABC (2017-09-12 13:09:23)

0

6

УДК 519.17 ББК 22.17 Ф69
Фляйшнер Г.
Ф69 Эйлеровы графы и смежные вопросы: Пер. с англ. — М.: Мир, 2002.— 335 с., ил.

ISBN 5-03-003115-4
Монография известного австрийского математика посвящена теории эйлеровых графов — одному из интенсивно развивающихся разделов тео¬рии графов. Это первая монография по данной теме. В книге собраны как классические, так и современные результаты в этой области, уделено внима¬ние алгоритмическим вопросам, сформулирован ряд нерешенных проблем. Изложение сопровождается большим количеством примеров и графических иллюстраций. В книгу включена впервые переведенная на русский язык основополагающая статья Эйлера 1736 г., посвященная известной задаче о кёнигсбергских мостах.
Книга будет полезна как специалистам в различных областях матема¬тики, так и всем, кто применяет теорию графов.
ББК 22.17 УДК 519.17
Федеральная целевая программа книгоиздания России
Герберт Фляйшнер Эйлеровы графы и смежные вопросы
Зав. редакцией академик В. И. Арнольд Зам. зав. редакцией А. С. Попов. Ведущий редактор Г. М. Цукерман Художник В. П. Григорьев Технический редактор О. Г. Лапко. Корректор Е. Н. Клитина Оригинал-макет подготовлен В. Н. Цлаф в пакете с использованием семейства шрифтов Computer Modern с кириллическим
расширением LH
Лицензия ЛР № 010174 от 20.05.97 г.
Подписано к печати 21.03.2002 г. Формат 70 х 100/16.
Печать офсетная. Объем 10,50 бум. л. Усл.-печ. л. 27,3. Уч.-изд. л. 23,64. Изд. № 1/9404. Тираж 3000 экз. Заказ № 5995
Издательство «Мир»
Министерства РФ по делам печати, ^ телерадиовещания и средств массовых коммуникаций 107996, ГСП-6, Москва, 1-й Рижский пер., 2.
Диапозитивы изготовлены в издательстве «Мир»
Отпечатано с готовых диапозитивов в ППП «Типография Наука».
121099, г. Москва, Шубинский пер., 6.
Редакция литературы по математическим наукам
ISBN 5-03-003115-4 (русск.) ISBN О 444 88395 9 (англ.)
Elsevier Science Publishers B.V., 1990
перевод на русский язык, издательство «Мир», 2002

Оглавление

От редактора перевода 5
Предисловие    8
Глава I. Введение 11
Глава II. Три столпа теории эйлеровых графов     15
Решение одной задачи, связанной с геометрией положения      16
О возможности обхода линейного комплекса без повторений и прерываний 33
Из «Analysis situs» О. Веблена       38
Глава III. Основные понятия и предварительные результаты .,. ..... .40
III.1 Смешанные графы и их основные части    40 ..
III.2 Некоторые связи между графами и (смешанными) (ор)графами. Под¬графы      45
III.3 Графы, получающиеся из заданного графа 50
III.4 Маршруты, цепи, пути, циклы, деревья; связность    53
III,5 Совместимость, циклический порядок множества К* и соответствующие -
эйлеровы цепи     72
III.6 Паросочетания, 1-факторы, 2-факторы, 1-факторизации, 2-факторизаг ции, двудольные графы 75
III.7  Вложение графов в поверхности; изоморфизмы 81
III.8  Раскраска плоских графов 89
III.9  Гамильтоновы циклы 92
III.10  Матрицы инцидентности и смежности, потоки и напряжения 97
III.11  Алгоритмы и их сложность    100
III.12 Заключительные замечания    102
Глава IV. Характеризационные теоремы и их следствия 104
IV.1. Графы     104
IV.2. Орграфы   110
IV.3. Смешанные графы     113
IV.4  Упражнения       119
Глава V. Некоторые возможные обобщения    121
V.1 . Разложения на цепи, путевые/цикловые разложения 121
V.2. Результаты о четности    122
V.3. Двойные проходы   124
V.4. Пересечение границы: расщепления графов 124
V. Упражнения      126
Глава VI. Различные типы эйлеровых цепей 127
VI. 1. Эйлеровы цепи, избегающие некоторых переходов 127
VI.2. Попарно совместимые эйлеровы цепи 155
VI.3. A-цепи в плоских графах 183
V1.4. Упражнения    266
Глава VII. Преобразования эйлеровых цепей  270
VI.1. Преобразование произвольных эйлеровых цепей в графах 271
VII.2. Преобразование эйлеровых цепей специального типа   276
VII.3. Преобразование эйлеровой цепи в орграфах 304
VII.4. Заключительные замечания и некоторые открытые проблемы 309
VII.5. Упражнения 311
Список литературы 314
Предметный указатель     329

///////////////////////////////////////////////////////////////////////////////////////////////

0

7

УДК 681.3.06+519.6 ББК 32.81 К28
Касьянов В. Н., Евстигнеев В. А.
К28 Графы в программировании: обработка, визуализация
и применение
. — СПб.: БХВ-Петербург, 2003. — 1104 с.: ил.
ISBN 5-94157-184-4
I
Книга содержит изложение фундаментальных основ современных ком¬пьютерных технологий, связанных с применением теории графов. Приведены основные модели, методы и алгоритмы прикладной теории графов. Рассмотрены задачи рисования графов и визуальной обработки графовых моделей. Описаны области приложения, такие как хранение и поиск информации, трансляция и оптимизация программ, анализ, преобразование и распараллеливание программ, параллельная, и распределенная обработка информации. В книге используется высокоуровневое описание алгоритмов, позволяющее понять алгоритм на содержательном уровне, оценить пригод¬ность его для решения конкретной задачи и осуществить модификацию ал¬горитма, не снижая степень математической достоверности окончательного варианта программы.

^ Для научных работников, инженеров, преподавателей, аспирантов
и студентов естественно-научных специальностей
УДК 681.3.06+519.6 ББК 32.81
Группа подготовки издания:
Главный редактор Екатерина Кондукова
Зам. главного редактора Анатолий Адаменко
Зав. редакцией Григорий Добин
Редактор Полина Столбова
Компьютерная верстка Ольги Сергиенко
Корректор Зинаида Дмитриева
Дизайн обложки Игоря Цырульникова
Зав. производством Николай Тверских
Лицензия ИД № 02429 от 24.07.00. Подписано в печать 23.05.03.
Формат 70x100 1/16. Печать офсетная. Усл. печ. л. 89.
Тираж 3000 экз. Заказ Ne 202 "БХВ-Петербург", 198005, Санкт-Петербург, Измайловский пр., 29.
Гигиеническое заключение на продукцию, товар № 77.99.02.953.Д 001537.03.02 от 13.03.2002 г. выдано Департаментом ГСЭН Минздрава России.
Отпечатано с готовых диапозитивов в ФГУП ордена Трудового Красного Знамени Техническая книга" Министерства Российской Федерации по делам печати, телерадиовещания и средств массовых коммуникаций 198005, Санкт-Петербург, Измайловский пр., 29.
' ISBN 5-94157-184-4
Касьянов В. Н., Евстигнеев В. А., 2003 © Оформление, издательство "БХВ-Петербург”, 2003

Скачать

https://yadi.sk/d/VxL0IBtG3N9p2H

0

8

П. Камерон, Дж. Ванн. Линг

ТЕОРИЯ ГРАФОВ
ТЕОРИЯ КОДИРОВАНИЯ
И БЛОК СХЕМЫ

Перевод с английского
1980 МОСКВА «НАУКА»

Скачать
https://yadi.sk/d/fsFmtT3z3N9n96

0

9

Свами М.   Тхуласираман К.
Графы, сети и алгоритмы: Пер. с англ.— М.: Мир,
1984.— 455 стр.

Скачать
https://yadi.sk/d/hY7PS2vv3N9qUZ

\

0

10

Т. Ху

ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ И ПОТОКИ В СЕТЯХ
Редактор И. А. Маховая. Художник Н. С. Хмелевская. Художественный редактор В. И. Шаповалов. Технический редактор Г. Б. Алюлина. Корректоры К. Л. Водяницкая и Н. А. Гиря
Сдано в набор 25/XII 1973 г. Подписано к печати 8/V 1974 г. Бумага кн. журя. 60x901/16 = 16,25 бум. л. 32,50 печ. л. Уч.-изд. л. 23,67
Цена 2 р. 14 к. Зак. 01348
ИЗДАТЕЛЬСТВО «МИР», Москва, 1-й Рижский пер#, 2
Ордена Трудового Красного знамени Московская типография № 7 «Искра революции» Союзполиграфпрома при Государственном комитете Совета Министров СССР по делам издательств, полиграфии и книжной торговли, г. Москва, К-1, Трехпрудный пер., 9
ОГЛАВЛЕНИЕ

Предисловие редактора перевода . .           5

Из предисловия автора .      . .

Глава 1. Основные понятия . .       13

1.1. Задачи линейного программирования . . . . . . ... . 13
1.2. Эквивалентные формулировки     15.
1.3. Неравенства . . 18   
1.4. Конусы, выпуклые множества и выпуклые функции . . : . 23
1.5. Базисные, допустимые и оптимальные решения . ...33
1.6. Геометрическая интерпретация задачи линейного программирования .....     40
Упражнения    . 41

Глава  2. Симплекс-метод       . . 44

1.1. Введение ....      44 .
2.2. Таблица симплекс-метода .  48
2.3. Начальный допустимый базис и вырожденность . . . ... 53.
2.4. Симплекс-метод в матричной форме записи .  61
2.5. Геометрическая интерпретация симплекс-метода 63
2.6.  Экономическая интерпретация симплекс-метода 66
Упражнения ... . . .... .  68
Дополнение    69. . .

Глава 3. Двойственность      . . . . 70

3:1. Теорема двойственности (Гейл, Кун, Таккер) [71]) . .70 J
3.2. Дополняющая нежесткость (Данциг и Орден [44]).75 .
3.3. Ортогональность решений (Таккер [193]) 77
3.4. Геометрическая интерпретация двойственности и дополняю-
щей вежесткости (Гомори [83]) 81
Упражнения   84
Дополнение .  85

Глава  4. Двойственный симплекс-метод     86

4.1. Двойственный симплекс-метод (Лемке [141]) .. .... 86
4.2. Столбцовая таблица (Бил [8]) . . ..... 89
4.3. Геометрическая интерпретация (Лемке [141J) ....... 96
Упражнения . . . . . . . . ... .    . . . . . . . 99

Глава 5. Модифицированный смиплекс-метод . 100

5.1. Введение (Данциг и Орчард-Хейс 143]) . . . 100
5.2.  Изменение исходной информации . .. . . 106
Упражнения   107     

Глава 6. Метод одновременного решения прямой и двойственной  задач 109

6.1. Взаимный метод решения прямой и двойственной задач (Балинский и Гомори [7] и Тролл [184]) .... . ... . . . 109
6.2. Прямо-двойственный метод (Данциг, Форд и Фалкерсон [40]) 117

Глава 7. Принцип декомпозиции  125

7.1. Принцип декомпозиции (Данциг и Вулф [46/,  [47]). . . 125
7.2. Пример    . 129
Упражнения , . .    . 132
Дополнение . .     133-

Глава 8. Максимальный поток . .     134

8.1  Введение . .       134
8.2 Метод расстановки пометок для нахождения максимальной потока    142
8.3. Приложения  152
8.4.  Линейное программирование и потоки в сетях     156
8.5.  Свойство абсолютнрй унимодулярности (Гофман, Краскал [103], Вейнотт, Данциг [199]) ... . . . . . . . . . . . . 159"
Упражнения   162
Дополнение     J ... . 163

Глава 9. Многополюсные максимальные потоки . . . . . . . ... 164

9.1. Постановки задач . . .   164
9.2. Условие реализуемости (Гомори и Ху [89]) ........ 165
9.3. Анализ сети (Гомори и Ху [89]) ............. 167
9.4. Синтез сети (Гомори и Ху [89])      189
Упражнения   188:
Дополнение . . . . . . . . . . ......  189
Нерешенные задачи . ...................  489

Глава 10. Кратчайшие цепи и потоки минимальной стоимости ... 191

10.1. Кратчайшие цепи (Дийкстра [49])     191
10.2. Многополюсные кратчайшие цепи (Флойд [63], Ху [111], Мерчленд [158], Уоршелл [209])   193
10.3. Декомпозиционный алгоритм (Ху [111], [113]) ...... 203
10.4. Потоки минимальной стоимости . ... ... . ... . . 212
10.5. Задачи об оптимальном преобразовании заданной сети (Фалкерсон [68], Ху [108]) .    213
Упражнения       221

Глава 11. Многопродуктовые потоки ............... 223

11.1. Двухпродуктовые потоки (Ху [106]) 223
11.2. Многопродуктовые потоки (Форд и Фалкерсон [66], Томлин [186]) - . . . . ........ 239
11.3. Синтез коммуникационных сетей (Гомори и Ху [91]) . . . 243
Глава. 12. Потоки в непрерывной среде    . 265
12.1. Локально минимальные разрезы  265
12.2. Сети с пропускными способностями узлов ........ 267
12.3. Потоки в непрерывной среде  272
r-разделяющее множество .    273

Глава 13. Циклический алгоритм целочисленного программирования 284

13.1. Введение (Гомори [79]) . . .     . 284
13.2. Примеры (Гомори [79])    291
13.3. Геометрическая интерпретация    295
13.4. Свойства дополнительных неравенств (Гомори и Баумоль
[87])    296

Глава 14. Полностью целочисленный алгоритм .......... 300

14.1. Полностью целочисленный алгоритм (Гомори [80]) .... 300
14.2. Пример ... 308

Глава 15. Смешанный алгоритм целочисленного программирования . 310

15.1. Введение (Гомори [81])    310
15.2. Метод разбиения в смешанном целочисленном программировании (Бендере [18])   315
15.3. Приложения      323

Глава 16. Целочисленное программирование с параболическими ограничениями      ....... . . . 331

16.1. Введение (Витцгалл [215])     . . . 331
16.2. Таблица     334
16.3. Преобразование    335
16.4. Алгоритм . .      . 337
16.5. Примеры . . . . . . . . . . . . . . . . . . . . . ... 333
16.6. Доказательство конечности . . .   . 343

Глава  17. Прямой алгоритм целочисленного программирования
(Р. Д. Юнг) .       . .... . . ... 344

17.1. Введение и алгоритм   344
17.2. Пример      357
17.3. Доказательство конечности 360
17.4. Вывод соотношений и пояснений . ... . . . . 365

Глава  18. Задача о рюкзаке    371

18.1. Задача о рюкзаке (Гилмор, Гомори [75], Гомори [84]) . . . 371

Глава  19. О соотношении между линейным и целочисленным программированием     378

19.1. Введение (Гомори [84], Кортанек и Ярослав [133]) .... 378
19.2. Асимптотический алгоритм (Гомори [84], [85], [86]) .... 387
19.3. Алгоритм групповой минимизации (Ху [112])   414

Глава 20. Грани целочисленного многогранника . . 424

20.1. Введениеа    . .       . 424
20.2. Вычисление грани   432:
20.3. Многогранники Р (G, g0)   434
20.4. Автоморфизмы главных многогранников   437
20.5. Грани многогранников циклических групп   444
20.6. Грани многогранников гомоморфных групп 443
20.7. Характеры и неравенства   445
Приложение А. Нормальная форма Смита (Ху [112]) . ........ 450
Приложение В. Альтернативное доказательство двойственности . . 456
Приложение С. Алгоритмы типа дерева поиска ....... . . . 460
Приложение D. Грани, вершины и матрицы инциденций многогран¬ников     465
Список литературы   496
Список дополнительной литературы .... . ... ... 511






||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Указатель .      513
УДК 51(0.062) ББК22.1 М63
М63 Мир математики: в 40 т. Т. 11: Клауди Альсина. Карты метро и нейронные сети. Теория графов. / Пер. с исп. — М.: Де Агостини, 2014. — 144 с.
Наш мир полон не только букв и цифр, но и самых разных изображений. Это картины, фотографии, произведения искусства, многочисленные схемы... Вспомните схему вашей линии метро или автобусного маршрута — это всего лишь линия с точками, рядом с которыми подписаны названия остановок. Подобные схемы из точек и линий называются графами. Именно о них вы узнаете, прочитав эту книгу.
ISBN 978-5-9774-0682-6 УДК 51(0.062)
ISBN 978-5-9774-0702-1 (т. И) ББК 22.1
Claudi Alsina, 2010 (текст)
RBA Coleccionables S.А., 2011  ООО «Де Агостини», 2014
Иллюстрации предоставлены: age fotostock, Getty Images.

Содержание

Предисловие 11

Глава 1. Знакомство с графами 13
Из Кёнигсберга с любовью 14
Азы теории графов 18
Геометрические и полные графы 23
‘ Плоские графы 23
Задача о колодцах и враждующих семьях 26
Деревья, за которыми виден лес 28
Графы в повседневной жизни 33

Глава 2. Графы и цвета   39
Карты и цвета 39
Раскраска графа в два или три цвета 41
Четырех цветов достаточно 43
Хроматическое число     47

Глава 3. Графы, циклы и оптимизация 51
Эйлеровы циклы   51
Задача китайского почтальона 53
Гамильтоновы циклы 54
Задача коммивояжера 56
Критические пути 58
Графы и планирование: система PERT 59
Схема анализа по системе PERT 60

Глава 4. Графы и геометрия    65
Живительная формула Эйлера 66
Формула Эйлера для граней и вершин 69
Всегда существует треугольная, четырехугольная или пятиугольная грань 71
Все стороны различаются между, собой? Это невозможно! 75
Графы и мозаики 75
Другие геометрические задачи с графами 79
Гамильтоновы циклы в многогранниках 79
Графы на неплоских поверхностях 81
Конечные геометрии 82

Глава 5. Удивительные способы применения графов   85
Графы и интернет 85
Графы в физике и химии 87
Графы в архитектуре 89
Графы в урбанистике 95
Графы в социальных сетях   97
«Маленький мир» Стэнли Милгрэма 99
Графы и расписания 99
NP-полные задачи ' 101
Занимательные графы 102
Кто назовет 20? 103
Лабиринт в саду Роуз Болла   103
Игра «змейка» 104
Изящная нумерация графа 104
Ханойские башни 105
Игра Ним 106
Две цепи Мартина Гарднера 106
Цепь в прямоугольнике 106
Цепь на квадратной сетке 107
Маршрут коня на шахматной доске   108
Льюис Кэрролл и эйлеровы графы 109
Задача о четырех окружностях 110
Магические звезды 110
Магическая гексаграмма 111
Теория графов в школе 113
Графы и нейронные сети   115
Графы и линейное программирование 118

Эпилог 125

Приложение. Графы, множества и отношения 127
Отношения эквивалентности   130
Отношение порядка 131
Отображения 132
Нечеткие множества и графы 135

Словарь 137

Библиография   139

Алфавитный указатель   141

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Олег Евгеньевич Акимов
Дискретная математика: логика, группы, графы, фракталы
Художник: Н.П. Сивоглазов Корректор: В.И. Петрова Компьютерная верстка: А.А. Кандыба
Подписано в печать 2.10.2004. Формат 60 х 90i/i6. Гарнитура Newton. Бумага офсетная. Печать офсетная. Уел. печ. л. 41. Тираж 3 ООО экз. Заказ 5631
Издатель АКИМОВА E-mail: akimov_ol@mail.ru.
Отпечатано с CD во ФГУП ИПК «Ульяновский Дом пе 432980, г. Ульяновск, ул. Гончарова, 14
Предисловие — 3
1. Логика — 5

1. 1. Операции логики Буля — 5
• Диаграммы Эйлера — Венна — 5
• Объединение. Таблицы истинности — 6
• Пересечение, двойственность и дополнение — 7
• Стрелка Пирса, штрих Шеффера и разность — 9
• Симметрическая разность и эквивалентность — 11
1.1. Формы представления булевых функций — 12
• Совершенные формы представления — 12
• Минимизация булевых функций по Куайну — 15
• Минимизация по методу сочетания индексов — 17
• Минимизация по картам Карно — 18
• Базовые наборы булевых функций — 19
1.2. Методы доказательства в логике Буля — 22
• Основные законы логики Буля — 22
• Аксиоматический и конструктивный способы обоснования
• Примеры доказательств булевых тождеств — 27 .
• Практические задания по логике Буля — 31
1. 4. Введение в логику высказываний — 42
• Высказывания и операции над ними — 42
• Парадоксальные высказывания — 45
• Построение доказательств в логике высказываний — 48
• Аксиома порядка и ее применение — 50
• Табличный способ доказательства — 54
• Метод резолюций — 58
• Метод Вонга — 61
• Метод натурального исчисления (метод Генцена) — 62
• Практические задания по логике высказываний — 65
• Примеры решения задач — 73
1.5. Операции над предикатами и кванторами — 81
• О предикатах, кванторах и многоместных функциях — 81
• Конкретизация предикатов — 84 -
• Решетки вообще и булеан в частности — 90
• Построение доказательств в логике предикатов — 95
• Практические задания по логике предикатов —105
• Разбор решений задач по логике предикатов — 112

2. Группы —119

2.1. Группа и связанные с ней понятия — 119
• Линейное преобразование — 119
• Определение группы и примеры групп — 124
• Действия с 0,'1-матрицами — 130
• Обобщенное комплексное число — 131
• Гиперкомплексные числа —134
• Матричные конструкции — 137
• Подстановки —144
• Циклическая форма подстановок — 146
• Комбинаторные свойства подстановок — 150
2.2. Группы на матрицах и подстановках— 152
• Представления групп до 11 -й порядка — 152
• Группа 12-го порядка и групповые закономерности — 157
• Отношение эквивалентности — 163
• Факторгруппа, инвариант и внутренний автоморфизм — 168
• Голоморфы диэдра и кватерниона — 171
• Геометрическая интерпретация групповых преобразований -176
• Прямая сумма и прямое произведение — 183
• Размерность представления и диаграммы Юнга — 191
• Представления группы квадрата — 194
• Представления группы кватерниона — 196
• Октава и алгебра Клиффорда — 199
• Представления диэдров 5-го и 6-го порядков — 200
• Представления групп тетраэдра, куба и икосаэдра — 203
2.3. Групповые решетки из подгрупп — 212
• Отношение порядка — 212
• Решетки групп с 1 -го по 12-й порядок — 215
• Решетки групп 16-го порядка — 221
• Группа вращения декартовых координат и ее подгруппы — 232
• Решетки групп 18-го и 20-го порядков — 237
• Решетки групп 24-го порядка — 239
• Решетки групп 27-го порядка — 246
2.4. Алгебраические системы на базе групп — 250
• Какие бывают алгебраические системы — 250
• Числовые поля — 255
• Сведения из теории чисел — 260
• Поля многочленов — 263
• Разложение многочлена на неприводимые множители — 270
• Примеры разложения многочленов — 272
• Корректирующие коды — 276
• Порождающая и проверочная матрицы — 278
• Кодовое расстояние и помехозащищенность — 280
• Примеры корректирующих кодов — 283
2.5. Пространственные группы и двойственность — 287
• Группы Ли и Галуа — 287
• Симметрия уравнений Максвелла — 289
• Инвариантность волнового уравнения — 291
• Преобразование комплексной плоскости — 294
• Г руппа проективных преобразований и ее подгруппы — 296
• Две симметрии: вращение и перемещение — 298
• Двойственность и Проецирование — 300
• Ортогональные и гиперболические преобразования — 305
• Масштаб осей при гиперболическом повороте — 308
• Моделирование волновых процессов — 311
• Практические задания по группам — 320

3. Графы — 324

Вводные замечания — 324
3.1. Группы цепей графа — 329
• Элементарная группа цепей и ее решетка — 329
• Группа цепей тетраэдра — 332 '
• Классы эквивалентности группы цепей тетраэдра — 334
• Решетка группы цепей тетраэдра — 337
• Группа цепей куба — 339
• Гиперкуб, образованный из 72-х цепей куба — 341
• Классы эквивалентности группы цепей куба— 344
• Классы и подгруппы группы цепей Г5 — 349
• Задача Гамильтона о цепях додекаэдра — 354
3.2. Морфология графа — 363
• Матрицы смежности и инцидентности — 363
• Пути и контуры в графе — 365
• Симметрия графа и его дополнения — 367
• Виды графов — 370
• Разложение графа на базисные составляющие — 373
• Реберные и вершинные покрытия — 379
• Трансверсаль, мат^оид и двойственность графов — 382
• Отношения эквивалентности и порядка — 388
• Оптимальный путь и максимальный поток — 395
3.3. Кодирование, автоматы и группы на графах — 398
• Типы и назначение кодирования — 398
• Оптимальные деревья кодирования — 401
• Автоматы задержки и распознавания символов — 407
• Автоматы-преобразователи — 411
• Ликвидация эквивалентных состояний —415
• Г рафы кватерниона и тетраэдра — 418
3.4. Лингвистические и поисковые графы —423
• Порождающая грамматика — 423
• Граф словообразования — 427
• Г раф словоизменения — 434
• Задача о ханойской башне — 445
• Другие поисковые задачи — 449
3-5. Раскраска графов и вопросы топологии — 453
• Задача о раскраске карты — 453
• Аналогия с Великой теоремой Ферма — 456
• Планарные графы на торе — 460
• Многогранники — 463
•, Формула Эйлера и связанность поверхности — 466
• «Кренделя» и странные свойства гептаэдра — 469
• Формула для минимального числа цветов — 472
• Бутылка Клейна и вывернутые поверхности — 474
• Зацепления, узлы и топология — 476
• Практические задания по графам — 481

4. Фракталы — 491

4.1. Что такое фрактал — 491
4.2. Прямое произведение и фракталы — 495
4.3. К вопросу о размерности — 503
4.4. Грамматика на службе у фракталов — 514
4.5. Аффинные преобразования — 519
4.6. Динамические фракталы — 525
4.7. Динамика популяций — 541
4.8. Бифуркационная диаграмма — 546
4.9. Аттрактор «Крепостная стена» — 556
4.10. Тригонометрическая функция — 566
4.11. Прокол аттрактора — 579
4.12. Ноль-аттрактор, л-аттракторы и квазиаттракторы — 591
4.13. Субаттракторы — 602
4.14. Хаос —620

Библиография — 649

Отредактировано ABC (2017-09-23 22:03:32)

0

11

22.174
0-65
УДК 519
О р е О. Теория графов.—2-е изд.—М.: Наука, Главная редакция фи¬зико-математической литературы, 1980, 336 с.
Первые пять глав посвящены наглядному материалу и содержат ос-новные понятия и свойства графов. В шестой главе даются основы тео¬рии вполне упорядоченных можеств, которая используется в дальней¬шем для строго абстрактного рассмотрения бесконечных графов. Осо¬бенно подробно, в главе 7, излагается вопрос о паросочетаниях; естественным ее продолжением является глава 12. В главах 8—11 рас-сматриваются ориентированные графы, и затем на языке ориентированных графов изучаются частично упорядоченные множества. Последние три, очень интересные, главы (13—15) снова имеют дело с более на¬глядным материалом.
Книга дает достаточно полное представление о направлениях иссле» дований в теории графов; приводятся упражнения и нерешенные задачи; сделана попытка ввести систематическую терминологию. Напи¬сана книга ясным и достаточно доступным математическим языком. Она интересна п нужна специалиетам-математикам, инженерам, зани¬мающимся прикладными задачами, и студентам старших курсов уни¬верситетов и технических вузов.
Библ,— свыше 200 назв. Ил л. 88.

Ойстин Оре Ф
ТЕОРИЯ ГРАФОВ М., 1980 г., 336 стр. с илл.
ИБ № 11700
4-я типография издательства «Наука»,
630077, Новосибирск, 77, Станиславского, 25,

Редактор И. М. Овчинникова Технический редактор Е. В. Морозова Корректор Я. Б. Румянцева
Сдано в набор 12.12.79. Подписано к печати 11 06.80. Бумага 84х1087з2. тип. № 1. Обыкновенная гарнитура. Высокая печать. Условн. печ. л. 17,64. Уч.-изд. л. 17,18. Тираж 29 000 экз. Заказ №791. Цена книги 1 р,50 к.
Издательство «Наука»
Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15




ОГЛАВЛЕНИЕ

От редактора русского перевода . . 8

Предисловие   9

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ . . .... . 11

4.1. Определения  11     i l1
1.2. Локальные степени 16
1.3. Части и подграфы     22
1.4. Бинарные отношения     25
1.5. Матрицы смежности и инцидентности. . . 30

Глава 2. СВЯЗНОСТЬ . .     34

2.1. Маршруты, цепи и простые цепи ..... 34
2.2. Связные компоненты . . . . . . .    36
2.3. Взаимно однозначные отображения .... 39
2.4. Расстояния .41
2.5. Протяженность    45
2.6. Матрицы и цепи. Произведение графов ... 48
2.7. Головоломки   51

Глава 3. ЗАДАЧИ О ЦЕПЯХ  53

3.1. Эйлеровы цепи 53
3.2. Эйлеровы цепи в бесконечных графах 58
3.3. О лабиринтах . . . 64
3.4. Гамильтоновы циклы    70

Глава 4. ДЕРЕВЬЯ ........... 77

4.1. Свойства деревьев . . .  77
4.2. Центры в деревьях . 82
4.3. Циклический ранг (цикломатическое число) . . 87
4.4. Однозначные отображения     88
4.5. Произвольно вычерчиваемые графы    96

Глава 5. ЛИСТЫ И БЛОКИ 101

5.1. Соединяющие ребра и вершины 101
5.2. Листы     . . . ... 105
5.3. Гомоморфные образы графа ....... 107
5.4. Блоки    109
5.5. Максимальные простые циклы  114

Глава 6. АКСИОМА ВЫБОРА . ....... 117

6.1. Полная упорядоченность    117
6.2. Принципы максимальности 120
6.3. Суммируемые по цепи свойства 123
6.4. Максимальные графы исключения ..... 126
6.5. Максимальные деревья . . . . . 128
6.6. Соотношения между максимальными графами 130

Глава 7. ТЕОРЕМЫ О ПАРОСОЧЕТАНИЯХ .... 134

7.1. Двудольные графы.. 134
7.2. Дефициты . . .    . . 138
7.3. Теоремы о паросочетаниях . ... 141
7.4. Взаимные паросочетания . ...... 145
7.5. Паросочетания в графах частного вида . . . 150
7.6. Двудольные графы с положительными дефицитами 155
7.7. Применения к матрицам ... , . . . 160
7.8. Чередующиеся цепи и максимальные паросочетания 167
7.9. Разделяющие множества    . . .    176
7.10. Совместные паросочетания    178

Глава 8. ОРИЕНТИРОВАННЫЕ ГРАФЫ . . . . . 184

8.1. Отношение включения и достижимые множества   184
b.z. Теорема о гомоморфизме . . . . . . . 189
8.3. Транзитивные графы и погружения в отношения упорядочения . 191
8.4. Базисные графы . . . . . . . . .    194
8.5. Чередующиеся цепи     .    198
8.6. Суграфы первой степени в графе . . . .    202

Глава 9. АЦИКЛИЧЕСКИЕ ГРАФЫ . , . . . . . 206

9.1. Базисные графы 206
9.2. Деформации цепей •     . 208
9.3. Графы воспроизведения ........ 211

Глава 10. ЧАСТИЧНАЯ УПОРЯДОЧЕННОСТЬ .... 216

10.1. Графы частичных упорядочений . . . . . 216
10.2. Представления в виде сумм упорядоченных множеств 217
10.3. Структуры и структурные операции. Отношения замыкания  223
10.4. Размерность в частичном упорядочении .    227

Глава 11. БИНАРНЫЕ ОТНОШЕНИЯ И СООТВЕТСТВИЯ'
ГАЛУА . ........... 232

11.1. Соответствия Галуа 232
11.2. Связи Галуа для бинарных отношений .    237
11.3. Отношения чередующегося произведения .    242
11.4. Отношения Феррерса 245

Глава  12. СВЯЗЫВАЮЩИЕ ЦЕПИ .    248

12.1. Теорема о секущих цепях  248
12.2. Вершинное разделение 252
12.3. Реберное разделение  254 .......
12.4. Дефицит .256 . ..........

Глава 13. ДОМИНИРУЮЩИЕ МНОЖЕСТВА, ПОКРЫВАЮЩИЕ
МНОЖЕСТВА И НЕЗАВИСИМЫЕ МНОЖЕСТВА

13.1. Доминирующие множества   
13.2. Покрывающие множества и покрывающие суграфы
13.3. Независимые множества . . . .
13.4. Теорема Турана 
13.5. Теорема Рамсея 
13.6. Одна задача из теории информации .

Глава 14. ХРОМАТИЧЕСКИЕ ГРАФЫ
. . . . . .
14.1. Хроматическое число .   
14.2. Суммы хроматических графов ....
14.3. Критические графы
14.4. Полиномы раскрашиваний   

Глава 15. ГРУППЫ И ГРАФЫ . . . . . .

15.1. Группы автоморфизмов
15.2. Цветные графы Кэли для групп . . . . .
15.3. Графы с заданными группами   
15.4. Реберные отображения . .......

Литература .
  ' . . . . .
Именной указатель
   
Предметный указатель     

0

12

http://s5.uploads.ru/t/jO9B8.jpg

http://s8.uploads.ru/t/yjHp0.jpg

http://s8.uploads.ru/t/43XEc.jpg

http://s7.uploads.ru/t/7DCEf.jpg

0

13

В. В. Белов, Е. М. Воробьев, В. Е. Шаталов


ТЕОРИЯ ГРАФОВ

Допущено Министерством высшего и среднего специального образования СССР
в качестве учебного пособия для студентов высших технических учебных заведений

МОСКВА «ВЫСШАЯ ШКОЛА» 1976

ОГЛАВЛЕНИЕ

Предисловие    3

Г лава I. Основные определения. Первые задачи теории графов  5
§ 1. Предварительные сведения из теории множеств.......
§ 2. Основные определения теории графов
§ 3. Задачи, послужившие основой графов ...

Глава П. Алгоритмические задачи  18

§ 1. Задачи о кратчайших путях . . . .
§ 2. Алгоритм построения эйлерова цикла
§ 3. Лабиринты . . .... . . .
§ 4. Алгоритмы теории графов ....

Глава III. Гомоморфизмы мультиграфов.
Группа авто¬морфизмов .

§ 1. Вспомогательные сведения  групп
§ 2. Гомоморфизмы, изоморфизмы и морфизмы графов .еории авто-

Глава IV. Циклы в графах.
Цикломатическое число

§ 1. Цикломатическое число  графа. Деревья
§ 2. База независимых циклов . . . .

Глава V. Топологические инварианты двумерных по¬верхностей    
§ 1. Эйлерова характеристика . . . .
.§ 2. Гомологии двумерных поверхностей

Глава VI. Раскраски графов. Хроматическое число .

§ 1. Вычисление хроматического числа задан¬ного графа    
§ 2. Оценка хроматического числа плоского графа ...   
Г лава VII. Ядро графа. Применение графов в теории игр

§ 1. Ядро графа и его свойства .
§2. Графы в теории игр . . .

Глава VIII. Транспортные сети ..

§ 1. Потоки на транспортных сетях . .
§ 2. Некоторые прикладные задачи . .
§ 3. Поток, насыщающий выходные дуги

IX Теорема о системе различных представителей
и ее приложение в теории графов. . . . 128

§ 1. Теорема о системе различных представителей и другие эквивалентные ей утверждения 128
§ 2. Эквивалентность теорем 1.1 —1.6 . 134
§3. Венгерский алгоритм .144
§ 4. Прикладные задачи на  паросочетания    150

Глава X. Гамильтоновы маршруты и задача о комми¬вояжере. . 168. . . .

§ 1. Гамильтоновы циклы и контуры . . 168
§ 2. Задача о коммивояжере .. . . 179
§ 3. Метод ветвей и границ 182

Глава XI. Элементы теории конечных автоматов. Матри-
цы смежности графов и операции над ними 199

§ 1. Некоторые понятия теории конечных
автоматов   199
§ 2. Матрицы смежности графов и операции
над ними    . . . . 206
§ 3. Разложение графов по операциям произ¬ведения и суперпозиции . 219

Глава XII. Производящие функции и их применение в
перечислительных задачах теории графов 226

§ 1. Рисуночные ряды и производящие функции  .... .226
§ 2. Задачи о размене  монет и рассечении многоугольников...... 231
§ 3. Перечисление корневых деревьев . 236

Глава XIII. Теорема Пойа 239

§ 1. Цикловой индекс группы подстановок
множества ........240
§ 2. Транзитивные множества группы под¬становок    245
§ 3. Классы эквивалентных отображений 248
§ 4. Вес и перечень фигур и конфигураций 252
§ 5. Теорема Пойа 254
§ 6. Цикловые индексы двух групп, часто
встречающихся в теории перечислений графов .    259

Глава XIV. Некоторые методы перечисления графов 262

§ 1. Перечисление графов с р вершинами и
к дугами   262
§ 2.Перечисление полностью   неориентированных графов с р вершинами и к реб¬рами    . . 266
§ 3. Перечисление маркированных графов 270
§ 4. Перечисление деревьев .... 274

Глава XV. Электрические цепи

§ 1. Коцепи в графе ....
§ 2. Применение графов в теории электрических  сетей .
§3. Матрицы, ассоциированные с группами одномерных и нульмерных
цепей графа

Литература   

Дополнение В. В. Белов, В. П. Маслов Теория комплексных марковских цепей . . .

Глава I. Комплексные марковские цепи и суммирование по  путям   

§ 1. Алгебра матриц и графы
§ 2. Суперпозиция  амплитуд  вероятностей  событий  по Фейнману и определение комплексной марковской цепи   309
§ 3. КМ-цепь фотона 326

Глава II. Диаграммы Фейнмана в теории возмущений КМ-
цепи и квантовой теории . . . . . . . 337

§ 1. Регулярная теория возмущений КМ-цепи. 339
§ 2. Диаграммы Фейнмана в нерелятивистской квантовой механике как диаграммы теории возмущений КМ-цепи в «р,E -представлении 363
§ 3. Диаграммы Фейнмана в квантовой теории  поля    378

Литература к дополнению . .    389

Владимир Владимирович БЕЛОВ,
Евгений Михайлович ВОРОБЬЕВ,
Виктор Евгеньевич ШАТАЛОВ

ТЕОРИЯ    ГРАФОВ

Редактор А. И. Селиверстова. Переплет художника В. Л. Ильичева. Художественный редактор В. И. Пономаренко. Технический редак¬тор Н. В. Яшукова. Корректор В. В. Кожуткина.
Сдано в набор 11/IX-75 г. Подп. к печати 16/IV-76 г. Формат 84Х108/З2. Бум. тип. № 1. Объем 12,25 печ. л- Уел. п. л. 20,58. Уч.-изд. л. 18,62. Изд. № ФМ-556. Тираж 20 000 экз. Цена 81 коп. Зак. 637.
План выпуска литературы издательства • «Высшая школа» (вузы и техникумы) на 1975 г. Позиция № 79.
Москва, К-51, Неглинная ул., д. 29/14, издательство «Высшая школа»
Ярославский полиграфкомбинат Союзполиграфпрома при Гм дарственном комитете Совета .Министров СССР по делам, издательств, полиграфии и книжной торговли.
150014, Ярославль, ул. Свободы, 97.

0

14

Александр Калманович Звоикин Сергей Константинович Ландо

ГРАФЫ НА ПОВЕРХНОСТЯХ И ИХ ПРИЛОЖЕНИЯ



Оглавление

Предисловие 11

Глава О. Введение: о чем эта книга 15

§0.1. Новая жизнь старой теории 15
§ 0.2. План книги 16
§ 0.3. Чего вы не найдете в этой книге 18

Глава 1. Созвездия, накрытия и карты 21

§1.1. Созвездия 21
§ 1.2. Разветвленные накрытия сферы 27
1.2.1. Первые определения  27
1.2.2. Накрытия и фундаментальные группы 29
1.2.3. Разветвленные накрытия сферы и созвездия 32
1.2.4. Поверхности 36
§1.3. Карты 40
1.3.1. Графы и карты 40
1.3.2. Карты: топологическое определение 42
1.3.3. Карты: перестановочная модель 46
§ 1.4. Картографические группы 52
§ 1.5. Гиперкарты 56
1.5.1. Гиперкарты и двудольные карты 56
1.5.2. Деревья 58
1.5.3. Приложение: линейные группы над конечными полями .... 62
1.5.4. Каноническая триангуляция 64
§ 1.6. Более трех перестановок 68
1.6.1. Прообразы звезды или многоугольника 69
1.6.2. Кактусы 70
1.6.3. Прообразы жордаиовой кривой 75
§ 1.7. Дополнительные конструкции 76
1.7.1. Накрытия поверхностей высших родов 76
1.7.2. Теорема Ритта 78
1.7.3. Симметричные и регулярные созвездия 81
§ 1.8. Римановы поверхности: общие сведения 84

Глава 2. Детские рисунки 92

§2.1. Введение: теорема Белого 92
§ 2.2. Плоские деревья и многочлены Шабата 93
2.2.1. Общая теория в применении к деревьям 93
2.2.2. Простые примеры 101
2.2.3. Дальнейшее обсуждение 106
2.2.4. Более сложные примеры 113
§ 2.3. Функции Белого и пары Белого 121
§ 2.4. Действие Галуа и его комбинаторные инварианты 127
2.4.1. Предварительные сведения 128
2.4.2. Инварианты Галуа 130
2.4.3. Две теоремы о деревьях 136
§2.5. Многоликие функции Белого 139
2.5.1. Оценка Дэвенпорта—Штотерса—Занье 139
2.5.2. Многочлены Якоби 144
2.5.3. Кривая Ферма 148
2.5.4. Гипотеза abc 150
2.5.5. Множества Жюлиа 152
2.5.6. Уравнение Пелля для многочленов 155
§ 2.6. Доказательство теоремы Белого 159
2.6.1. Часть «только если» теоремы Белого 159
2.6.2. Замечания по поводу части «только если» 161
2.6.3. Часть «если», или «очевидная» часть теоремы Белого 163

Глава 3. Введение в метод матричных интегралов 168

§3.1. Модельная задача: карты с одной гранью 168
§ 3.2. Гауссовы интегралы 173
3.2.1. Гауссова мера на прямой 173
3.2.2. Гауссовы меры на Rk 175
3.2.3. Интегралы от многочленов и формула Вика 175
3.2.4. Гауссовы меры на пространстве эрмитовых матриц 177
3.2.5. Матричные интегралы и склейки многоугольников 180
3.2.6. Вычисление гауссовых интегралов. Унитарная инвариантность 183
3.2.7. Вычисление интеграла для склеек с одной гранью 189
§3.3. Матричные интегралы для карт с несколькими гранями 191
3.3.1. Диаграммы Фейнмана 191
3.3.2. Матричный интеграл для произвольной склейки 192
3.3.3. Как избавиться от несвязных графов 195
§ 3.4. Перечисление раскрашенных графов 196
3.4.1. Двухматричные интегралы и модель Изинга 197
3.4.2. Задача Гаусса 199
3.4.3. Меандры 201
3.4.4. О перечислении меандров 202
§ 3.5. Вычисление матричных интегралов 204
3.5.1. Пример: вычисление объема унитарной группы 204
3.5.2. Обобщенные многочлены Эрмита 206
3.5.3. Плоские аппроксимации 208
§3.6. Иерархия Кортевега—де Фриза (КдФ) для универсальной одномат¬ричной модели 210
3.6.1. Особенности производящих функций 211
3.6.2. Оператор умножения на λ в двойном скейлинговом пределе . . 213
3.6.3. Одноматричная модель и иерархия КдФ 214
3.6.4. Построение решений иерархии КдФ по грассманиаиу Сато . . 217
§3.7. Физическая интерпретация 221
3.7.1. Математические связи между физическими моделями 221
3.7.2. Фейнмановские интегралы по путям и теория струн 222
3.7.3. Модели квантовой теории поля 224
3.7.4. Другие модели 225
§ 3.8. Приложение 226
3.8.1. Производящие функции 226
3.8.2. Связные и несвязные объекты 228
3.8.3. Логарифм степенного ряда и формула Вика 230

Глава 4. Геометрия пространств модулей комплексных кривых 234

§4.1. Общие сведения о нодальных кривых и орбифолдах 234
4.1.1. Дифференциалы и нодальные кривые 234
4.1.2. Квадратичные дифференциалы 237
4.1.3. Орбифолды 238
§ 4.2. Пространства модулей комплексных структур 243
§4.3. Компактификация Делиня—Мамфорда 245
§4.4. Комбинаторные модели пространств модулей кривых 249
§ 4.5. Орбифолдная эйлерова характеристика пространств модулей 255
§ 4.6. Индексы пересечения на пространствах модулей; уравнение струны
и дилатон-уравнение 260
§4.7. Иерархия Кортевега—де Фриза (КдФ) и гипотеза Виттена 268
§4.8. Модель Концевича 269
§4.9. Набросок доказательства Концевича гипотезы Виттена 274
4.9.1. Производящая функция для модели Концевича 274
4.9.2. Модель Концевича и теория пересечений 275
4.9.3. Модель Концевича и уравнение КдФ 278

Глава 5. Пространства Гурвица 280

§5.1. Отображение Ляшко—Лойенги (ЛЛ) и жесткая классификация мно¬гочленов общего положения 281
5.1.1. Отображение Ляшко—Лойенги 281
5.1.2. Построение отображения Л Л на пространстве многочленов . . 282
5.1.3. Доказательство теоремы Ляшко—Лойенги 284
§ 5.2. Жесткая классификация вырожденных многочленов и геометрия
дискриминанта 288
5.2.1. Дискриминант в пространстве многочленов и его стратифика¬ция 288
5.2.2. Формулировка перечислительной теоремы 290
5.2.3. Примитивные страты 291
5.2.4. Доказательство перечислительной теоремы 293
§ 5.3. Жесткая классификация общих мероморфных функций и геометрия
пространств модулей кривых 299
5.3.1. Формулировка перечислительной теоремы 299
5.3.2. Вычисления в случаях родов 0 и 1 300
5.3.3. Конусы и их классы Сегре 303
5.3.4.                   Конусы главных частей .- 305
5.3.4. Пространства Гурвица 308
5.3.5. Пополненные пространства Гурвица и стабильные отображе¬ния .  310
5.3.6. Продолжение отображения ЛЛ на пополненные пространства Гурвица 312
5.3.7. Вычисление старшего класса Сегре и окончание доказатель¬ства 314
§5.4. Действие группы кос 316
5.4.1. Группы кос 316
5.4.2. Действие группы кос на кактусах: общие сведения 320
5.4.3. Экспериментальные результаты 324
5.4.4. Примитивные и импримитивиые группы монодромии 328
5.4.5. Перспективы 335
§ 5.5. Мегакарты 339
5.5.1. Пространства Гурвица накрытий с четырьмя точками ветвле¬ния 339
5.5.2. Представление римаиовой поверхности Н в виде детского ри¬сунка 340
5.5.3. Примеры 342

Глава 6. Алгебраические структуры, связанные с вложенными графами 348

§6.1. Биалгебра хордовых диаграмм 348
6.1.1. Хордовые диаграммы и дуговые диаграммы 348
6.1.2. Четырехчленное соотношение 350
6.1.3. Умножение хордовых диаграмм 353
6.1.4. Структура биалгебры 354
6.1.5. Структурная теорема для биалгебры М 356
6.1.6. Примитивные элементы биалгебры хордовых диаграмм .... 358
§ 6.2. Инварианты узлов и происхождение хордовых диаграмм 360
6.2.1. Инварианты узлов и их продолжение на сингулярные узлы . . 360
6.2.2. Инварианты конечного порядка 363
6.2.3. Вывод одночленного и четырехчлеиного соотношений для ин¬вариантов 365
6.2.4. Хордовые диаграммы особых зацеплений 367
§ 6.3. Весовые системы 369
6.3.1. Структура биалгебры па модуле V инвариантов Васильева уз¬лов 369
6.3.2. Перенормировка 370
6.3.3. Весовые системы 372
6.3.4. Инварианты Васильева и другие инварианты узлов 374
§ 6.4. Построение весовых систем по графам пересечений 376
6.4.1. Функции Татта графов 377
6.4.2. 4-биалгебра графов 378
6.4.3. Биалгебра взвешенных графов 388
6.4.4. Построение инвариантов Васильева по 4-инвариантам 392
§ 6.5. Построение весовых систем с помощью алгебр Ли 393
6.5.1. Свободные ассоциативные алгебры 394
6.5.2. Универсальные обертывающие алгебры алгебр Ли 395
6.5.3. Примеры 398
§6.6. Некоторые другие алгебры вложенных графов 401
6.6.1. Круговые диаграммы и открытые диаграммы 402
6.6.2. Алгебра 3-графов 403
6.6.3. Алгебра Темперли—-Либа 404

Приложение А. Д. Загир. Применения теории представлений конечных групп 406

§ А. 1. Теория представлений конечных групп 406
А. 1.1. Неприводимые представления и характеры 406
А. 1.2. Примеры 410
А.1.3. Формула Фробениуса 413
§ А.2. Приложения 416
А.2.1. Представления группы 8П и канонические многочлены, сопо¬ставляемые разбиениям 416
А.2.2. Примеры 422
А.2.3. Первое приложение: перечисление склеек многоугольников . . 424
А.2.4. Второе приложение: формула Гульдена—-Джексона 425
А.2.5. Третье приложение: «зеркальная симметрия»
в размерности один 430

Литература для приложения А 434

Приложение Б. М. Э. Казарян, С. К. Ландо. Алгебро-геометрическое доказательство гипотезы Виттена 436

§ Б. 1. Введение 436
§ Б.2. Иерархия Кадомцева—Петвиашвили и числа Гурвица 438
Б.2.1. Вложения грассмапиапов и уравнения Плюккера 438
Б.2.2. Пространство рядов Лорана 439
Б.2.3. Бозон-фермиониое соответствие 440
Б.2.4. Полубескопечный грассманиаи и уравнения КП 440
Б.2.5. Действие матричной группы 441
Б.2.6. Иерархия КП и г-КдФ иерархии 444
Б.2.7. Производящая функция для простых чисел Гурвица как ре¬шение иерархии КП 444
§Б.З. Доказательство гипотезы Виттена 447
Б.3.1. Выражение индексов пересечений '0-классов через числа Гур¬вица 448
Б.3.2. Вывод уравнения КдФ 451

Литература для приложения Б 451
Литература 453
Предметный указатель 470


Звонкин А. К., Ландо С. К.
343 Графы на поверхностях и их приложения. — М.: МЦНМО, 2010. - 480 с.

Графы, нарисованные на двумерных поверхностях, всегда привле¬кали исследователей своей красотой и разнообразием связанных с ними трудных вопросов. Теория таких графов, долгое время казавшаяся сравнительно изолированной, неожиданно оказалась в самом центре современных исследований.
Диапазон этих исследований простирается от теории Галуа до моделей квантовой гравитации. Книга представляет собой доступное введение в указанный круг вопросов. Она включает такие сюжеты, как накрытия римановых поверхностей, действие группы Галуа на вло-женных графах (гротендиковская теория «детских рисунков»), метод матричных интегралов, пространства модулей алгебраических кривых, топологические аспекты теории мероморфных функций, а также комбинаторные аспекты инвариантов Васильева.
ББК 22.151

Александр Калманович Звоикин Сергей Константинович Ландо

ГРАФЫ НА ПОВЕРХНОСТЯХ И ИХ ПРИЛОЖЕНИЯ
Издательство Московского центра непрерывного математического образования 119002, Москва, Большой Власьевский пер., 11. Тел. (499)241-74-83
Подписано в печать 27.04.2010 г. Формат 70x100 1/16- Бумага офсетная. Печать офсетная. Печ. л. 30. Тираж 400. Заказ № 3160
Отпечатано с готовых диапозитивов в ГУП «Типография „Наука"». 199034, Санкт-Петербург, В. О., 9 линия, 12.
Книги издательства МЦНМО можно приобрести в магазине «Математическая книга», Большой Власьевский пер., д. 11. Тел. (499)241-72-85.

0

15

Райгородский Андрей Михайлович

МОДЕЛИ СЛУЧАЙНЫХ ГРАФОВ


Оглавление

Предисловие 6

Глава 1
Некоторые основы теории вероятностей 8
1.1. Классическая вероятность 8
1.2. Схема Бернулли 9
1.3. Схема серий 11
1.4. Общее конечное вероятностное пространство 11
1.5. Условные вероятности и независимость событий 12
1.6. Несколько слов о бесконечных вероятностных пространствах 14
1.7. Случайные величины и их распределения 16
1.8. Моменты распределений 18
1.9. Формула обращения и предельные теоремы пуассоновского типа 21
1.10. Нормальная аппроксимация 24
1.11. Неравенства Чебышёва и Маркова 25
1.12. Уточнение неравенства Чебышёва в случае схемы Бернулли 26
1.13.  Условные вероятности и математические ожидания отно¬сительно разбиений 27
1.14. Понятие о мартингале 29
1.15.   Неравенство Азумы 29

Глава 2
Модель Эрдёша—Реньи случайного графа 32
2.1. Введение 32
2.2. Определение модели Эрдёша—Реньи 33
2.3. Одна естественная модификация модели 34
2.4. Треугольники в случайных графах 34
2.4.1. Постановка задачи и формулировки результатов ... 35
2.4.2. Доказательство теоремы 10 36
2.4.3. Доказательство теоремы 12 36
2.4.4. Доказательство теоремы 11 39
2.5. Связность случайного графа 42
2.5.1. Формулировки результатов и комментарии к ним . . 42
2.5.2. Доказательство теоремы 14 44
2.5.3. Вокруг теоремы 13 46
2.5.4. Гигантская компонента 47
2.6. Хроматическое число случайного графа 48
2.6.1. Определения, формулировки и комментарии  48
2.6.2. Мартингалы реберного и вершинного типов 51
2.6.3. Доказательство теоремы 18: формулировка леммы 1
и вывод из нее 51
2.6.4. Доказательство теоремы 18: доказательство леммы 1 54
2.6.5. Нижняя оценка в теореме 17 56
2.6.6. Верхняя оценка в теореме 17: план действий 58
2.6.7. Верхняя оценка в теореме 17: идея доказательства . . 58
2.6.8. Верхняя оценка в теореме 17: выбор параметров
и оценка вероятности 59
2.6.9. Верхняя оценка в теореме 17: доказательство леммы 2 60
2.6.10. Комментарий к лемме 2 63
2.6.11. Чем Yk лучше Хк, или почему не работает неравен¬ство Чебышёва? 64
2.6.12. О функции и в теореме 18 65
2.7. О числе независимости и кликовом числе случайного графа 66
2.8. Числа Рамсея 67
2.9. Хроматическое число и обхват графа 70
2.10. Законы нуля или единицы   72
2.10.1. Язык первого порядка для графов 73
2.10.2. Формулировки результатов 73
2.10.3. Игра Эренфойхта 74
2.10.4. Выигрышная стратегия для Консерватора 76
2.11. Еще ряд сюжетов 77
2.11.1. Деревья в случайных графах 77
2.11.2. Еще несколько слов о хроматическом числе случай¬ного графа 79
2.11.3. Планарность случайного графа 80
2.11.4. Степени вершин случайного графа 81
2.11.5. Изоморфизм случайных графов 82

Глава 3
Обобщенная модель Эрдёша—Реньи и случайные дистанционные графы 84
3.1. Определение модели 84
3.2. Случайные подграфы куба 85
3.3. Случайные дистанционные графы 87
3.4. Вспомогательные факты и свойства полного дистанционно¬го графа 88
3.4.1. Немного простой аналитики 88
3.4.2. О числе независимости полного графа расстояний . 89
3.4.3. О кликовом числе полного графа расстояний 91
3.4.4. О хроматическом числе полного графа расстояний . 92
3.4.5. О числе ребер в произвольном подмножестве множества вершин полного графа расстояний 94
3.4.6. «Олимпиадный» комментарий к предыдущему пункту 97
3.5. Хроматическое и кликовое числа дистанционного графа . . 99
3.6. Хроматическое число случайного дистанционного графа . . 103
3.7. Дистанционные числа Рамсея 103
3.7.1. Постановка задачи 103
3.7.2. Формулировки результатов 105
3.7.3. Доказательство теоремы 35 106
3.7.4. Доказательство теоремы 37 108
3.8. О связности случайного дистанционного графа 111
3.9. Законы нуля или единицы для случайного дистанционного графа 111

Глава 4
Модели случайных веб-графов 114
4.1. Наблюдения Барабаши—Альберт 114
4.2. Модель Боллобаша — Риордана 116
4.2.1. Динамическая модификация 116
4.2.2. Статическая модификация, или LCD-модель 117
4.2.3. Некоторые результаты 118
4.2.4. Доказательство теоремы 44 при к = 1 121
4.3. Модель копирования 127

Глава 5
Приложение 129
Литература 131

Райгородский Андрей Михайлович

МОДЕЛИ СЛУЧАЙНЫХ ГРАФОВ

Подписано в печать 13.07.2011 г. Формат 60 х 90 1/16- Бумага офсетная. Печать офсетная.
Печ. л. 8,5. Тираж 1000 экз. Заказ №
Издательство Московского центра непрерывного математического образования.
119002, Москва, Большой Власьевский пер., д. 11. Тел. (499) 241-74-83
Отпечатано с готовых диапозитивов в ООО «Типография ,,САРМА“».
Книги издательства МЦНМО можно приобрести в магазине «Математическая книга», Большой Власьевский пер., д. 11.
Тел. (499) 241-72-85. E-mail: biblioamccme.ru

0

16

22.18 Е 26
УДК 519.6
Евстигнеев В. А. Применение теории графов в программировании./

Под ред. А. П. Ершова,— М.: Наука. Главная редакция физико-математической литературы, 1985—352 с.
Книга посвящена вопросам использования методов теории графов для исследования структуры сложных программ, определения их параметров, верификации, организации хранения и поиска информации, распределения памяти и для рещения других вопросов, возникающих в системном программировании и смежных областях.

Владимир Анатольевич Евстигнеев

ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В ПРОГРАММИРОВАНИИ

Серия «Библиотечка программиста»
Редактор Н. В. Полякова
Техн. редактор В. Я. Кондакова
Корректоры Т. С. Плетнева, М. Л. Медведская
ИВ М 12380
Сдано в набор 16.05.84. Подписано к печати 15.01.85. Т-01212. Формат 84X108732. Бумага тип. М 3. Обыкновенная новая гарнитура. Высокая печать. Уел. печ. л. 18,48. Уел. кр.-отт. 18,69, Уч.-изд. л, 18,96, Тираж 20 000 экз, Заказ М 223. Цена 1 р. 20 к,
Издательство «Наука»
Главная редакция физико-математической литературы 117071 Москва В-71, Ленинский проспект, 15
4-я типография издательства «Наука»
630077 г, Новосибирск, 77, ул, Станиславского, 25

Издательство «Наука», Главная редакция физико-математической литературы, 1985




ОГЛАВЛЕНИЕ

От редактора 5

Предисловие  .    7

Глава 1. Основные понятия    9

§ 1. Основные определения теории графов ... 9
§ 2. Графы как модели программ, данных и процессов 19
§ 3. Графы как объекты обработки информации . . 26
Библиографический комментарий   32

Глава 2. Глобальный анализ графов ...33

§ 1. Нумерации, выявляющие логическую структуру
графа 33
§ 2. Логический анализ управляющих графов. Линей¬ные компоненты и компоненты сильной связности 52
§ 3. Гамаки, полугамаки и шлейфы 76
§ 4. Интервалы и сводимые графы 83
§ 5. Контуры в орграфах 105
Библиографический комментарий 118

Глава 3. Итеративные алгоритмы глобального анализа
графов. Пути и покрытия 121

§| 1. Итеративный алгоритм Килдала .. 121
§ 2.  Пути в орграфах 130
§ 3.Пути, удовлетворяющие дополнительным ограни¬чениям. Покрытия 138
§ 4.  Отыскание доминаторов в орграфе .... 150
Библиографический комментарий 165

Глава 4. Оптимизационные задачи на графах    166

§ 1. Построение оптимальных нумераций .... 166
§ 2. Конструирование оптймалйных деревьев ... 192
§ 3. Балансированные деревья , . . . 214
Библиографический комментарий 239

Глава 5. Разрезания и раскраска графов                          241

§ 1. Разрезания графов                                                                       241
§ 2. Раскраска графов    278
Библиографический комментарий 292

Глава 6. Применение теории графов в  программировании   294

§ 1. Анализ и тестирование программ. Вычисление характеристик программ  294
§ 2. Применение методов теории графов к органпзации вычислительного процесса  309    °
§ 3. Применение деревьев для организации больших 
массивов информации  325

Библиографический комментарий                              340

Список литературы ' ' ' ' ' 342

Предметный указатель   350

0

17

http://s3.uploads.ru/t/tN6Bj.jpg

http://s7.uploads.ru/t/3hZ2O.jpg

Скачать книгу
https://yadi.sk/d/6w7yMuV6OqcVUQhttps:/ … MuV6OqcVUQ

0


Вы здесь » поговорим о ЛОНИИС » Теория графов » Книги по теории графов - оглавления