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

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

УДК 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)

УДК 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)

УДК 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

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

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

\

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. Реберные отображения . .......

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

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

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

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

МОСКВА «ВЫСШАЯ ШКОЛА» 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.

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

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

Оглавление

Предисловие 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

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