Название:

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

Описание: Ф. Харари, Э. Палмер Перечисление графов Перевод с английского Г. П. Гаврилова Издательство «МИР» Москва 1977 Скачать бесплатно

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

 

 

ОГЛАВЛЕНИЕ
Предисловие переводчика . 5
Предисловие 7
Глава 1. ПЕРЕЧИСЛЕНИЕ ПОМЕЧЕННЫХ ОБЪЕКТОВ ... 11
1.1 Число способов, которыми можно пометить граф 12
1.2. Связные графы 16
1.3. Блоки 19
1.4. Эйлеровы графы 22
1.5. Число /с-раскрашенных графов 27
1.6. Ациклические орграфы 30
1.7. Деревья 32
1.8. Эйлеровы контуры в орграфах 38
Упражнения 43
Глава 2. ТЕОРЕМА ПОЙА 46
2.1. Группы и графы 47
2.2. Цикловой индекс группы подстановок 49
.2.3. Лемма Бернсайда 53
2.4. Теорема Пойа 57
2.5. Ряд 1 + а: — специальный ряд для фигур 62
2.6. Взаимно однозначные функции 64
Упражнения 67
Глава 3. ДЕРЕВЬЯ 69
3.1. Корневые деревья 69
3.2, Некорневые деревья 73 
3.3. Деревья со специальными свойствами  78
3.4. Древовидные графы 89
3.5. 2-деревья 95
Упражнения 102
Глава 4. ГРАФЫ 104
4.1. Графы 105
4.2. Связные графы ИЗ 
4.3. 2-раскрапшгаые графы 117
4.4. Корневые графы 124
4.5. Надграфы и раскрашенные графы 129
4.6. Булевы функции 136
4.7. Эйлеровы графы 141
Упражнения 145
Глава 5. ОРГРАФЫ 147
5.1. Орграфы 148
5.2. Турниры 153
5.3. Ориентации графа 157
5.4. Смешанные графы 159
Упражнения 163
Глава 6. ПЕРЕЧИСЛЕНИЕ СТЕПЕННОЙ ГРУППЫ 165
6.1. Теорема перечисления степенной группы 165
6.2. Самодополнительныо графы 168
6.3. Взвешенные функции 171
6.4. Графы с раскрашенными ребрами 175
6.5. Конечные автоматы 177
6.6. Самообратные орграфы 182
Упражнения 188
Глава 7. СУПЕРПОЗИЦИЯ 190
7.1. Теорема перечисления Редфилда 190
7.2. Теорема декомпозиции Редфилда 194
7.3. Графы и орграфы 200
7.4. Обобщение теоремы перечисления Редфилда 202
7.5. Общие графы 206
Упражнения 210
Глава 8. БЛОКИ 211
8.1. Обобщение леммы Редфилда 211
8.2. Композиция групп 212
8.3. Теорема композиции 215
8.4. Связные графы 217
8.5. Суммы цикловых индексов корневых графов 219
8.6. Блоки 220
8.7. Графы с данными блоками 223 
8.8. Ациклические орграфы 227
Упражнения 230
Глава 9. АСИМПТОТИКА 231
9.1. Графы 232
9.2. Орграфы 235
9.3. Графы с данными числами вершин и ребер , 237 
9.4. Связные графы и блоки 241 
9.5. Деревья 245
Упражнения 252
Глава 10. НЕРЕШЕННЫЕ ЗАДАЧИ 254 
10.1. Помеченные графы 254 
10.2. Орграфы 255 
10.3. Графы с данными структурными свойствами 257 
10.4. Графы с данным параметром 261 
10.5. Подграфы данного графа 266
10.6. Надграфы данного графа 268
10.7. Графы и раскраска 269
10.8. Вариации на тему о графах 271
Приложение I 280
Приложение II 287
Приложение III 289
Список литературы 292
Именной указатель 301
Предметный указатель 304
Указатель обозначений 311

 

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Мы приводим в тексте определения почти всех понятий, используемых в этой книге. Для удобства читателя некоторые понятия определялись несколько раз. Все они помещены в этом указателе. Терминология согласуется с той, которая принята в книге Харари [1J.
Абсолют корневого дерева (absolute of a rooted tree) 84
— реберно-корневого дерева (of a line rooted tree) 84
Автомат (automaton) 178
Автоматы изоморфные (isomorphic automata) 178
Автоморфизм графа (automorphism of graph) 14, 48
Блок (block) 20

Булева функция (boolean function) 136
Вершина графа (point of a graph) 12
— инцидентная дуге (incident with a arc) 15
ребру (with a line) 12
— орграфа (of a digraph) 15
— покрывает ребро (covers line) 263

— смежная к вершине (adjacent to a point) 15
Вершины смежные (adjacent points) 12
— соединены ребром (join by a line) 12

Вес вершины дерева (weight of a point of a tree) 102

— дерева (of a tree) 102
— орбиты (of a orbit) 56, 58, 172
— функции (of a function) 58
Весовая функция (weight function) 55, 58, 172
Взвешенная форма леммы Бернсайда (weighted form of Burnside's ) 56
Входной алфавит автомата (input alphabet of an automaton) 178
Высота корневого дерева (height of a footed tree) 103
Выходной алфавит автомата (output alphabet of an automation) 178
Гипотеза четырех красок (four color conjecture) 269
Граф (graph) 12
Граф асимметрический (identity) 242 
— блоков (block) 92
— вершинно-симметрический (point-symmetric) 146, 260
— галшльтонов (hamiltonian) 258
— двойственный к плоскому графу (dual of a plane graph) 271
— двумерный решетчатый (two-dimensional lattice) 279
— знаковый помеченный (signed labeled) 43
— интервалов (interval) 261
— клик (clique) 261
— корневой (rooted) 17
— локально ограниченный (locally restricted) 112
— направленный (oriented) 157
— — помеченный (labeled) 43
— неразложимый (non-separable) 20
— обладающий квадратным корнем (which has a square root) 260
— общий (general) 206
— ориентированный (directed) 15, 147
— плоский (plane) 44
— подразбиений (subdivision) 261
— полный (complete) 38
— — двудольный (bipartite) 118
— — m-дольный (m-partite) 134
— помеченный (labeled) 13
— раскрашенный (colored) 27
— реберно-симметрический (line-symmetric) 260
— реберный (line) 260
— решетчатый d-мерный (d-dimensional lattice) 279
— самодополнительный (self-complementary) 168
— самонегативнып (self-negational signed) 189
— сбалансированный (balanced signed) 146
— связный (connected) 16
— симметрический (symmetric) 260
— с корнем (rooted) 17
— смешанный (mixed) 159
— снабженный знаками (signed) 146
— тождественный (identity) 242
— тотальный (total) 261
— узла, узловой (knot) 273

— унициклический (unicyclic) 89
— — помеченный связный (labeled connected) 45
— циклически жесткий (rigid circuit) 261
— четный (even) 22
— эйлеров (eulerian) 22, 141
— 2-раскрашенный (bicolored) 117
— 2-раскрашиваемый (bicolorable) 124
— к -раскрашенный (к -colored) 27, 117
— m-раскрашенный (m-colored) 129, 132, 133
— m-раскрашиваемый (m-colorable) 136
— п-раскрашиваемый (те-colorable) 266
— ге-связный (rc-connected) 263
— гс-хроматический (rc-chromatic) 266
Графы корневые изоморфные (isomorphic rooted graphs) 17
— помеченные изоморфные (isomorphic labeled) 13
— fc-раскрашешше изоморфные (isomorphic fc-colored) 27
— эквивалентные относительно дополнительности (equivalent up to complementation) 169
Группа автоморфизмов графа (automorphism group of a graph) 48
— графа (of a graph) 14, 48
Группа графа вершинно-реберная (point-liue): 131
— — реберная (line) 106
— диэдральная (dihedral) 51
— единичная (identity) 51
— знакопеременная (alternating) 50

— матричная (matrix) 202
— орграфа (of a digraph) 15
— парная (pair) 106
— подстановок на множестве объектов (permutation group with object set) 47
— производная (derived) 197
— редуцированная упорядоченная парная (reduced ordered pair) 147, 148
— симметрическая (symmetric) 49
— степенная (power) 57
— триадная (triad) 272
— упорядоченная парная (ordered pair) 152
— циклическая (cyclic) 51
Группы подстановок идентичные (identical permutation groups) 49
— — изоморфные (isomorphic) 48
Декартово произведение групп (cartesian product of groups) 119
Дерево (tree) 32
— асимметрическое (identity) 83

— блоков и точек сочленения (block-cutpoint) 92
— взвешенное (weighted) 102
— входящее (to a point) 38
— выходящее (from a point) 38
— гомеоморфно несводимое (homeomorphically irreducible) 81
— данного веса (of given weight) 87
— данной мощности (of given strength) 87, 102
— двумерное (two-dimensional) 96
— корневое данной высоты (rooted, with given height) 103
— непомеченное (unlabeled) 69
— ориентированное (oriented) 78
— остовное (spanning) 37

— плоское (plane) 87
— с висячим корнем (planted) 79
данной степенной спецификацией (with a given degree specification) 86, 102
— — данным разбиением (with a given partition) 86, 102
— смешанное (directed) 86
— снабженное знаками (signed) 87, 102
— Хусими (Husimi) 93
Диаметр графа (diameter of a graph) 262
— дерева (of a tree) 102
Дополнение графа (complement of a graph) 48, 168
— орграфа (of a digraph) 170, 183
Древесностъ графа (arboricity of a graph) 264
Дуга инцидентная вершине (incident with a point) 15
— орграфа (arc of a digraph) 15
— последняя (exit) 42 1
Задача Изинга (Ising problem) 279
— о ладьях (roock) 275
— — росте клеток (cell growth) 276
— — ферзях (queens) 276
Звездный многоугольник (starred polygon) 43

Знак графа (sign of a graph) 24 1
Изоморфизм графов (isomorphism of graphs) 14
Источник автомата (source of an automaton) 180
— орграфа (of a digraph) 256
Кактус (cactus) 93
— помеченный (labeled) 45
— треугольный (triangular) 93
Каркас (spanning tree) 37
Квадрат графа (square of a graph) 260
Класс подобных блоков (class 01 simmilar blocks) 73
Клика графа (clique of a graph) 261
Комплекс симплициальный (simplicial complex) 271
— — чистый двумерный (pure two-dimensional) 146, 252
Композиция групп (composition of groups) 121
Компонента графа (component of a graph) 17
— орграфа сильная (of a digraph, strong) 156
Конденсация орграфа (condensation of a digraph) 156, 255
Контур (cycle) 30
Корень графа (root of a graph) 17
Крупность графа (coarseness of a graph) 265
Латинский квадрат (Latin square) 272
Лемма Бернсайда (Burnside's lemma) 54
— пересчета помеченных графов (labeled counting lemma) 18
— Редфилда (Redfield's lemma) 195
Лес (forest) 76
Маршрут длины п (walk of length n) 16
— — — ориентированный (directed) 30
— замкнутый (closed) 30
Матрица смежности помеченного графа (adjacency matrix of a labeled graph) 37
Матрицы, эквивалентные по столбцам (column equivalent matrices) 192
Матричная теорема о деревьях для графов (matrix-tree theorem for graphs) 37
— — — — — орграфов (digraphs) 39
Мультиграф (multigraph) 111
— данной мощности (of given strength) 146
— 2-раскрашенный (bicolored) 206
Надграф (supergraph) 129
Недревесность графа (anarboricity of a graph) 265
Независимое множество вершин (independent set of points) 263
— — ребер (of lines) 263
Обобщение теоремы перечисления Редфилда (a generalization of Redfield's enumeration theorem) 202
Обобщенная композиция групп (generalized composition group) 213
Обращение цикла подстановки (converse of a cycle of a permutation) 154
Обход графа (girth of a graph) 262
Ограниченная форма леммы Бернсайда (restricted form of Burnside's lemma) 55
Окружение графа (circumference of a graph) 262
Орбита (orbit) 53
Орграф (digraph) 15
— ациклический (acyclic) 30
— вершинно-симметрический (point-symmetric) 164
— гамильтонов (hamiltonian) 258
— обратный к данному орграфу (converse of given digraph) 182
— односторонне связный (unilaterally connected) 256
— односторонний (unilateral) 256
— полный (complete) 162
— самообратный (self-converse) 182
— связный (connected) 152
— сильно связный (strongly connected) 155, 255

— сильный (strong) 155, 255
— слабо связный (weakly connected) 152
— соответствующий графу (of a graph) 157
— транзитивный (transitive) 256
— функциональный (functional) 90
— — помеченный связный (labeled connected) 44
— эйлеров (eulerian) 40
Орграфы итерированные реберные (iterated line digraphs) 45
— эквивалентные относительно обращения (equivalent up to conversion) 183
Ориентация графа (orientation of a graph) 157
Ортогональные латинские квадраты (orthogonal Latin squares) 273
Остов (spanning tree) 37
Перечисляющий ряд для конфигураций (configuration counting series) 58
— — — фигур (figure) 58
— — — функций (function) 58
Петля (loop) 12
Площадь четного подграфа двумерной решетки (area «f an evee subgraph of a two-dimensional lattice) 279
Подграф (subgraph) 17
— остовный (spanning) 37

— покрывает граф (spans the graph) 37
— порожденный (induced) 125
Подграфы неподобные (dissimilar subgraphs) 117
Полимино квадратное (square animals) 276
— неодносвязное (holey) 277
— односвязное (simply connected) 277 
— тороидальное (toroidal) 278
— треугольное (traingular) 278
— шестиугольное (hexagonal) 278
Полиномиальная форма теоремы перечисления степенной грушш (polinomUl form of the power group enumeration theorem) 189 .
Полустепень захода (indegree) 15
— исхода (outdegree) 15
Порядок графа (order of a graph) 12
— группы (order of a group) 47
Проблема ожерелья (necklace problem) 60, 62
Произведение групп (product of a groups) 52
— — веночное (wreath) 121
Производящая функция (generating function) 13
— — экспоненциальная (exponential) 18
Радиус графа (radius of a graph) 262
Разбиение графа (partition of a graph) 12
— дерева (of a tree) 102
— цветное (color) 133
Размерность комплекса (dimension of a complex) 272
— симплекса (of a simplex) 272
Расширение орграфа (extension of a digraph) 30
Ребра кратные (multiple lines) 12
Ребро графа (line of a graph) 12 
— дерева симметричное (of a tree, symmetry) 74
— инцидентное вершине (incident with a point) 12
— покрывает вершину (covers point) 263
— соединяет вершины (joins points) 12
— торцевое (end-line) 97
Род графа (genus of a graph) 265
Ряд, перечисляющий конфигурации (configuration counting series) 58
— — фигуры (figure) 58
— — функции (function) 58
Связность (connectivity) 263
— реберная (line-connectivity) 263
Сеть (net) 179
Симплекс (simplex) 272
Система транзитивности группы (transitivity system of a group) 53
Сложность графа (complexity) 265
Состояние автомата (state of an automaton) 178
— — заключительное (terminal) 180
— — начальное (initial) 180
Стабилизатор элемента (stabilizer of an element) 53
Степень вершины (degree of a point) 22
— группы подстановок (of a permutation group) 47
Сток орграфа (sink of a digraph) 256
Сумма цикловых индексов всех графов данного множества (cycle index sum of the groups of all graphs in given set) 215
Суперпозиция графов (superposition of graphs) 190, 192
Теорема декомпозиции Редфилда (Redfield's decomposition theorem) 195
— композиции (composition) 216
— о характеристике неподобия для графов (dissimilarity characteristic theorem for graphs) 73
— — — — — деревьев (trees) 75
— — — — — кактусов (cacti) 94
— — — — — 2-деревьев B-trees) 96
— перечисления для 2-деревьев (enumeration theorem for 2-trees) 99
— — Пойа (Polya's enumeration) 58
Редфилда (Redfield's) 192
— — степенной группы, константная форма (power group, constant form) 167
— — — — форма степенного ряда (power series form) 174
Толщина графа (thickness of a graph) 265
Точка комплекса (point of a complex) 271
— сочленения (cutpoint) 19
Триангуляция многоугольника (triangulation of a polygon) 99
Тройка транзитивная (transitive triple) 153
— циклическая (cyclic) 153
Турнир (tournament) 16, 153
Удаление вершины из графа (removal of a point from a graph) 19
Факторизация графа (factorization of a graph) 267
Формула обращения Лагранжа (Lagrangc's inversion formula) 35, 36
Формула Оттера (Otter's) 75
Функции, эквивалентные относительно группы (equivalent functions with respect to group) 215
Функция выходов (output function) 178
— класса (class function) 195, 199
— переходов (input function) 178

Хроматический индекс (chromatic index) 266
Цвет вершины (color of a point) 27
Цепь (trail) 16

— простая (path) 16
Цикл подстановки самообратный (self-converse cycle of a permutation) 154
— типа 1 (type-1) 94
— типа 2 (type-2) 94
Цикловой индекс группы подстановок (cycle index of a permutation group) 49
Число вершинного покрытия (point-covering number) 263
— независимости вершинное (point-independence) 263
— — реберное (line) 263
— пересечения (intersection) 264
— реберного покрытия (line-covering) 263
— реберно-хроматическое (line-chromatic) 266
— скрещиваний (crossing) 265

— тотально-хроматическое (total-chromatic) 266
— хроматическое (chromatic) 265 
Эйлеров контур (eulerian trail) 40
Эквивалентность относительно (Bi, В2, . . ., Вт) (equivalence with respect to (Bi, B2, . . ., Bm)) 192

Экспоненциация групп (exponentiation of groups) 123
Эксцентриситет вершины (eccentricity of a point) 262
Элементы подобные (similar elements) 53

Ячейка (cell) 96  

 

 

 

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

 

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