Алгоритмы в теории графов

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

Author(s): Плесневич Г.С., Сапаров М.С.
Year: 1981

Language: Russian
Pages: 313
City: Ылым

Титульный лист......Page 1
Аннотация и выходные данные......Page 2
ВВЕДЕНИЕ......Page 3
ГЛАВА 1. КРАТЧАЙШИЕ ПУТИ В ГРАФЕ. ДОСТИЖИМОСТЬ И СВЯЗНОСТЬ......Page 7
Определение ориентированного графа и теоретико-графовых понятий......Page 8
Понятие алгоритма; о языке представления алгоритмов......Page 14
Алгоритм A1 для построения графа кратчайших путей......Page 15
Алгоритм А2 для нахождения кратчайшего пути между заданными вершинами......Page 16
Сложность вычисления, временная сложность алгоритма относительно базиса операций......Page 19
Теорема 1.1 о корректности и об оценке сложности алгоритма А2......Page 22
Теорема 1.2 о корректности и сложности алгоритма А2......Page 23
Алгоритм A3 для выяснения достижимости; теорема 1.3 о корректности и сложности алгоритма A3......Page 24
Алгоритм А4 (Дейкстры) для нахождения длин кратчайших путей во взвешенном графе......Page 25
Алгоритм А5 ддя нахождения кратчайшего пути между заданными вершинами во взвешенном графе......Page 26
Теорема 1.4 о корректности и оценке сложности алгоритма А4......Page 31
Определение неориентированного и обыкновенного графов......Page 34
Алгоритм А6 для отыскания метрики обыкновенного графа......Page 36
Теорема 1.5 о корректности алгоритма А6......Page 37
Теорема 1.7 о сложности алгоритма А6......Page 39
Граф перестановок......Page 44
Алгоритм А7 дня выяснения связности неориентированного графа......Page 45
Машина Тьюринга и о ее работе......Page 46
Понятия о полиномиальных и экспоненциальных алгоритмах и различия между ними......Page 54
О приложениях......Page 59
ГЛАВА 2. ЦИКЛЫ И ДЕРЕВЬЯ......Page 61
Теорема 2.1 о критерии существования эйлерова цикла в неориентированном графе......Page 62
Теорема 2.2 (Эйлера) для ориентированных графов......Page 63
Алгоритм А8 для отыскания эйлерова цикла в неориентированном графе......Page 64
Теорема 2.3 об оценке сложности алгоритма Эйлера......Page 68
Приложение теоремы и алгоритма Эйлера к задаче построения полных двоичных последовательностей......Page 69
Гамильтоновы циклы......Page 71
Алгоритм А9 для перечисления $n$-перестановок в соответствии со свойствами их смежности......Page 72
Теорема 2.4 о корректности алгоритма А9......Page 73
Алгоритм A10 для отыскания в связном обыкновенном графе гамильтонова цикла методом "проб и ошибок"......Page 75
Теорема 2.5 о нижней оценке сложности алгоритма A10......Page 78
Об экспоненциальном характере нижней оценки для отыскания гамильтонова цикла......Page 80
Алгоритм A11 для отыскания гамильтонова цикла в связном обыкновенном графе......Page 82
Теорема 2.6 об оценке сложности алгоритма A11 и его корректности в классе графов с большими степенями......Page 85
Теорема (Дирака) о гамильтоновых циклах как следствие теоремы 2.6; гамильтонова цепь и понятия о деревьях......Page 90
Алгоритм A12 для отыскания в связном обыкновенном графе гамильтоновой цепи......Page 95
Протокол вычисления по алгоритму A12......Page 96
Протокол нерезультативного вычисления по алгоритму A12......Page 99
О графе Татта......Page 103
Алгоритм A14 (Краскала) для нахождения покрывающего дерева наименьшего веса в связном взвешенном графе......Page 106
Теорема 2.7 о корректности и об оценке сложности алгоритма Краскала......Page 108
О приложениях......Page 110
ГЛАВА 3. ПАРОСОЧЕТАНИЯ И ВНУТРЕННЕ УСТОЙЧИВЫЕ МНОЖЕСТВА......Page 112
Двудольный граф......Page 113
Паросочетания, чередующиеся пути, цепи, циклы. Лемма 1 о критерии максимальности паросочетания......Page 114
Алгоритм A15 для нахождения наибольшего паросочетания в обыкновенном графе и теорема A15 о временной сложности алгоритма A15......Page 117
Лемма 2 о размере тупиковых паросочетаний в $n$-вершинном графе......Page 118
Алгоритм A16 цля поиска пополняющей цепи......Page 120
Бихроматические графы; теорема 3.2 (Д.Кенига) о критерии бихроматичности графа......Page 125
Теорема 3.3 о корректности в классе бихроматических графов......Page 126
Теорема 3.4 о сложности алгоритма A16......Page 130
Алгоритм A17 для нахождения реберного покрытия наименьшего размера. Теорема 3.5 о корректности алгоритма A17......Page 131
Задача нахождения наибольшего (по числу ребер) подграфа с заданными границами для степеней......Page 132
Теорема 3.5 и алгоритм A18 для нахождения наибольшего подграфа с заданными границами для степеней......Page 136
Теорема 3.6 (Кенига-Холла)......Page 137
Проблема о реберной раскраске неориентированного графа......Page 139
Теорема 3.7 (В.Г.Визинга) и теорема 3.8 о хроматическом индексе бихроматического графа......Page 140
Алгоритм A19 для минимальной раскраски ребер двудольного графа. Теорема 3.9 о полиномиальности алгоритма A19......Page 142
О вершинной раскраске обыкновенного графа......Page 143
Внутренне устойчивые множества, ядра и опоры обыкновенного графа......Page 144
Алгоритм А20 для нахождения всех ядер в обыкновенном графе......Page 146
Теорема 3.10 о корректности алгоритма А20......Page 147
Теорема 3.11 об оценке сложности алгоритма А20......Page 150
О реберных графах......Page 151
Полиномиальная сводимость и разрешимость задач......Page 152
Недетерминированный алгоритм A21......Page 154
Протокол вычисления по недетерминированному алгоритму A21......Page 155
Теорема 3.12 о понятии проблемы разрешения......Page 162
Алгоритмы А22 и А23 для перехода от одной задачи разрешения к другой......Page 164
Недетерминированный алгоритм А24 для решения проблемы разрешения......Page 165
Теорема 3.13 о полиномиальной разрешимости......Page 166
Теорема 3.14 о полиномиальном сведении проблем разрешения, ассоциированная с хроматическим числом, к проблеме разрешения числа внутренней устойчивости и декартова произведения обыкновенных графов......Page 167
Полиномиальное сведение задачи об изоморфном вложении к задаче о числе внутренней устойчивости......Page 169
Теорема 3.15 (Визинга В.Г.) о существовании изоморфного вложения графа в граф......Page 171
Теорема 3.16 (В.Г.Визинга) о существовании слабоизоморфного вложения графа в граф......Page 172
Теорема 3.17 о полиномиальной сводимости задач к задаче, ассоциированной с числом внутренней устойчивости......Page 173
Реккурентные функции на графах......Page 185
Деревья разборки......Page 186
Алгоритм А25 для вычисления произвольной бинарной рекуррентной функции......Page 188
Лемма об устранимых вершинах графа......Page 194
Алгоритм А26 (ЧИСТКА)......Page 195
Алгоритм А27 для вычисления нижней оценки......Page 196
Алгоритм А28 для вычисления верхней оценки......Page 198
Лемма о корректности алгоритма А28......Page 199
Алгоритм А29 для нахождения числа внутренней устойчивости методом ветвей и границ......Page 200
Протокол вычисления по алгоритму А29 для случайного графа......Page 208
Протокол вычисления по алгоритму А29 дня графа группы......Page 212
О приложениях......Page 214
ГЛАВА 4. ПОКРЫТИЯ И ГИПЕРГРАФЫ......Page 216
О числе внешней устойчивости......Page 217
Основные понятия теории гиперграфов......Page 218
Формулировка задачи о покрытии в виде задачи целочисленного линейного программирования......Page 221
Теорема 4.1 о $Np$-полноте задачи о покрытии......Page 222
О поглощении вершин......Page 224
Алгоритм А30 (#ЧИСТКА)......Page 225
Алгоритм A31 для вычисления верхней оценки числа покрытия двудольного графа......Page 229
Алгоритм А32 для вычисления нижней оценки числа покрытия двудольного графа......Page 231
Понятия из теории гиперграфов, обобщающие соответствующие теоретико-графовые понятия......Page 238
Теорема 4.2 (Х.Уитни) о реберном изоморфизме обыкновенных графов......Page 243
Теорема 4.3 об изоморфизме нормальных $D$-представлений......Page 245
Алгоритм А34 для распознавания свойства особенностей ребер гиперграфов......Page 262
Алгоритм А35 для "разрушения" особых ребер в гиперграфе......Page 264
Алгоритм А36......Page 265
Алгоритм А37......Page 267
Алгоритм А38 для нахождения нормального $D$-представления гиперграфа......Page 268
Алгоритм А39 для нахождения числа внутренней устойчивости гиперграфа......Page 273
О приложениях......Page 275
ГЛАВА 5. СЛУЧАЙНЫЕ ГРАФЫ......Page 280
Случайные обыкновенные графы......Page 283
Теорема 5.1 (П.Эрдеша и А.Реньи) о предельном распределении, касаюшегося связности случайного графа......Page 285
Теорема 5.3 (Р.Карпа) о средней степени вершины в случайном графе......Page 286
Теорема 5.4 о среднем числе точных покрытий двудольного графа......Page 288
Теорема 5.6 о среднем размере тупиковых покрытий......Page 295
О приложениях......Page 304
ЛИТЕРАТУРА......Page 305
СОДЕРЖАНИЕ......Page 308
Выходные данные......Page 312
Обложка......Page 313