Название:

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

Описание: Многогранники, графы, оптимизация (комбинаторная теория многогранников). Емеличев В. А., Ковалев М. М., Кравцов М. К. — М.: Наука. Главная редакция физико-математической литературы, 1981. — 344 с. Скачать бесплатно

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

 

 

 

 

 

ОГЛАВЛЕНИЕ
Введение 6
Глава. I. Выпуклые многогранники 13
1. Выпуклые множества 13
2. Выпуклые многогранники 18
3. Операции над многогранниками 25
4. Многогранник решений системы линейных неравенств ...... 30
5. /-вектор многогранника 39
Задачи н дополнения 47
Глава II. Графы многогранников . . . 52
§ 1. Связность полиэдральных графов 52
§ 2. Диаметр многогранника 59
Задачи и дополнения 71
Глава III. Комбинаторные свойства граничных комплексов многогранников , 74
11. Комбинаторные типы многогранников . . 74
2. Диаграммы Гейла 82
3. Максимальное число граней 88
4. Минимальное число граней 97
Задачи и дополнения 103
Глава IV. Целые точки полиэдров 106
1. Целочисленные решения систем линейных неравенств 107
2. Условия целочисленности полиэдра 116
3. Абсолютно унимодулярные матрицы 119
4. Унимодулярные матрицы ннциденций 126
5. Многогранники покрытий, разбиений и упаковок ...... 135
6. Полиматроиды 142
. 7. Локально целочисленные многогранники 152
Задачи и дополнения 160
Глава V. Перестановочные многогранники 168
1. Многогранник бистохастических матриц 168
2. Многогранник гамильтоновых циклов 174
3. Перестановочный многогранник 181
4. Многогранник размещений 188
о 5. Многогранник задачи стандартизации 195
Задачи и дополнения 202
Глава VI. Классические транспортные многогранники 208
| 1. Основные определения и свойства 209
§ 2. Базисы и остовные деревья 212
3. Грани 215
4. Диаметр  . . . 218
5. Многогранники с минимальным числом вершин 227
в. Основные понятия 229
7. Многогранники с максимальным числом вершин 236
8. Подсчет числа <р(т, я) 244
9. Минимальное число вершин в классе невырожденных транспортных многогранников с заданным числом граней 249
§ 10. Асимптотика 252
Задачи и дополнения , , 255
Глава VII. Транспортные многогранники с дополнительными условиями , 267
§ 1. Усеченные транспортные многогранники , 267
§ 2. (к, <)-усеченные транспортные многогранники , , . , , 274
§ 3. Распределительный многогранник 280
Задачи и дополнения ........ 283
Глава VIII. Многой и дексные транспортные многогранники .,.,,,, 290
§ 1. Аксиальные транспортные многогранники 291
§ 2. Пленарные транспортные многогранники 298
§ 3. Планы многоиндексной проблемы выбора ............. 305
Задачи и дополнения ............................. 310
Проблемы, гипотезы 319
Литература , 322
Предметный указатель 334
Указатель обозначений 339

 

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Абсолютно уннмодулярная матрица 117
Абстрактная грань полуматроида 79, 105
Абстрактный комплекс 77
— многогранник 77
— симплекс 77
— симплициальный комплекс 77
Агрегирующее уравнение 113
Аксиальная проблема выбора 309
Аксиальный транспортный многогранник 291
Антиблокирующее множество 48
Антизвезда граничного комплекса 98
Антиизоморфизм многогранников 29
Аффинная оболочка множества 14
— комбинация точек 14
Аффинно зависимое множество точек 14
— независимое множество точек 14
— эквивалентные множества 13
Аффинное множество 13
— отображение (преобразование) 13
Аффинный базис множества 14
Ациклический турнир 205
База вектора 143
Базис матроида 34, 148
— многогранника 33
Базисная точка многогранника 48
Базисное множество вершины 211
— решение 33
Бесконечный спектр 234
Бистохастическая квадратная матрица 168
Бихроматический граф 128
Вектор мажорируется вектором 182,
Векторный матроид 34
Верхнее основание клина 63
Вершина графа 53
—, инцидентная ребру 53
— комплекса 77
— многогранника 18, 19
— пирамиды 42
— полуматроида 79
Вершинно непересекающиеся цепи графа 53
Вершинно-симметрический граф 172
Внешне устойчивое множество графа 136
Внешняя вершина связного комплекса 98
— грань графа 55
Внутренне устойчивое множество графа 136
подмножество вершин гиперграфа 125
Внутренность множества 16
относительно его аффинной оболочки 17
Внутренняя грань графа 55
Выпуклая комбинация точек 17
— оболочка множества 17
Выпуклое множество 15
Выпуклый конус 17
— многогранник 18
Вырожденная вершина 37, 210
— грань многогранника 49
— форма задания многогранника 37
Вырожденное аффинное отображение 13
— решение 37
Вырожденный многогранник 37, 210
Гамильтонов граф 69, 174
— контур 174
— цикл в графе 60, 174
Геодезическая линия в графе 57
Гиперграф интервалов 125
Гиперплоскость 15
— строго отделяет множество от множества 16
Гипотеза о максимальном диаметре 60
Граница выпуклого множества 17
— линзы 58
Граничный комплекс многогранника 74
Грань-диаметр многогранника 62
— графа 55
— многогранника 18, 216, 272
Грань-цепь многогранника 62
ДО
Граф 59
— многогранника 52
— пересечений булевой матрицы 138
— полиэдра 73
— полуматроида 105
Графический матроид 148
Двойственный многогранник 29
Двудольный граф 129
Диагональ матрицы 130
Диаграмма Гейла 84
— многогранника 36
Диаметр графа 59
— многогранника 9, 59
Дискретно-выпуклая функция 167
Длина цепи в гиперграфе 126
— цикла в гиперграфе 126
Дополнение графа 138
Допустимое базисное решение 36
— для множества проективное преобразование 26
Допустимый базис многогранника 36
Естественная реализация абстрактного
симплициального комплекса 78
Жесткое ограничение многогранника 31
Задача о назначениях 202
— о покрытии 135
— о разбиении 135
— о й-медиане графа 157
— об упаковке 135
Замкнутая геодезическая линия в графе 57
Зубчатая система множеств 181
Идеальная вершина 260
Избыточное ограничение 32
Изоморфные комплексы 74
— полуматронды 80
Инверсия 187
Источник орграфа 131
Каноническая форма системы кубов 307
Квазицелочисленный многогранник 152
Классическая транспортная задача 209
Классический транспортный многогранник 210
Клика графа 137
Кликоматическое число графа 139
Клнн 63
Когрань многогранника 83
Комбинаторно эквивалентные многогранники 75
Комплекс 74
— реализуется многогранником 75
Конечная проективная плоскость 309
Конечнопорожденная полугруппа 107
Конечный спектр 234
Коническая комбинация точек 17
Каноническая форма задания многогранника 31
Конус 17
—, порожденный множеством 17
Концевое подмножество 94
Коцикл матроида 166
Крайняя точка выпуклого множества
Критерий Данцига—Вейнотта 116
Критическая пара многогранника 217
Критически несовершенный граф 163
Латинский р-куб порядка я 305
Линейно зависимое множество точек 14
— независимые гиперплоскости 15
— независимое множество точек 14
Линза 58
Линия матрицы 129, 230
— /п-сочетаний 165
— р-куба 305
Максимальный пленарный граф 59
— подграф 53
— поток в орграфе 131
— элемент частично упорядоченного множества 142
Матрица клик графа 137
— /п-размещений 92
— ограничений многогранника 32
Матроид 34, 148
— разбиений 149
Метка в множестве Гейла 83
Метод наибольшего элемента 260
— северо-восточного угла 258
— северо-западного угла 258
Минимальный элемент частично упорядоченного множества 142
Многогранник ациклических турниров 205
— гамильтоновых контуров 175
—г — циклов графа 174
— задачи стандартизации 195
— квадратичной задачи выбора 205
— матроида 149
— медиан графа 157
— паросочетаний 140
— покрытий 136
— разбиений 136
— размещений 188
— реализует граф 52
— симметрических перестановочных матриц 173
— упаковок 136
— четных перестановок 187
— fc-сочетаний 165
Многогранный конус 18
Множество Гейла 83
— точек находится в общем положении
Направляющий вектор гиперплоскости 10
Невозвращающаяся цепь в графе многогранника 63
Невырожденная вершина 210
Невырожденное аффинное отображение 13
— проективное преобразование 25
— решение 37
Невырожденный многогранник 210
Нежесткое ограничение многогранника 31
Независимые множества матроида 148
Неколлинеарные элементы матрицы 129
Неограниченный перестановочный лиматроид 186
— полиматроид 143
Неприводимая линза 58
— система 32
Неприводимое, порождающее множество полугруппы 162
Несобственная грань многогранника 186
Нечетная перестановка 187
Нечетный цикл гнперграфа 126
Нижнее основание клина 63
Нормальная диагональная матрица НО
— система векторов 292
кубов 306
— форма задания многогранника 31
Обобщенный транспортный многогранник 288
Ограниченное множество 16
Ограниченный перестановочный полиматроид 186
— полнматроид 143
Одинаковая четность компонент вектора 119
Однопараметрическая задача стандартизации 201
Опорная гиперплоскость 16
Опорное полупространство 16
Оптимальное решение транспортной задачи 256
Орграф 131
Орразрез 165
Ортогональная система р-клубов 305, 306
Основание пирамиды 42
Особая вершина многогранника 245
Особое преобразование векторов 293
Особый многогранник 262
Остов конуса 18
Остовный подграф 53
Острый конус 18
Отделимые множества 15
Отделяющая гиперплоскость 15
Отрезок 16
Параллельные аффинные множества 13
Паросочетание графа 136
Переброска по циклу 219
Перестановочная матрица 168
Перестановочный многогранник 181
Пирамида 42
Планерная проблема выбора 309
— р-индексная транспортная задача 290
Пленарный граф 55
Плотность клики графа 138
Подграф 53
Подобные вершины графа 172
Покрытие множества 135
Полиэдр 15
Полиэдральная полугруппа 107
Полиэдральные последовательности 319
Полиэдральный конус 17
Полная матрица 199
Полный граф 71
— двудольный граф 129
Полуматроид 79
— многогранника 80
Поляра 26
Порождающее множество полугруппы 107
Порождающий набор 14
Порожденный подграф 53
Порядок конечной проективной плоскости 310
Помеченный многогранник 90
Поток в орграфе 131
Почти все транспортные многогранники обладают свойством  252
— нет транспортных многогранников, обладающих свойством  252
Правильно усеченныи транспортный многогранник 269
Правильное смещение вершины многогранника 60
Правильный (k, ^-усеченный транспортный многогранник 277
Приводимая система векторов 293
Проблема агрегации 113
Проективно единственный многогранник 104
Проективное преобразование 25
Проективный образ многогранника 26
Проекция точки 16
Произведение многогранников 25
Пропускная способность коцикла 166
орребра 131
разреза орграфа 131
Простая линия матрицы 230
— цепь в графе 53
Простой комплекс 103
— многогранник 24
— спектр 235
— цикл в графе 53
Прямое продолжение ребра в графе 57
Равномерное множество 161
Радиус многогранника 10
Разбиение множества 135
Развертка граничного комплекса многогранника 90
Разделяющее множество 99
Размерностно неопределенный комплекс 103
Размерность абстрактного симплекса 77
— выпуклого множества 16
— комплекса 74
— симплициального комплекса 77
Разрез орграфа 131
Ранг вектора 143
— матроида 34
— полуматроида 79
Ранговая функция полиматроида 143
Раскраска графа 128
Распадающаяся система векторов 293
Распределительный многогранник 280
Расстояние между вершинами связного графа 59
— от вершины до грани многогранника 65
Ребро графа 53
— многогранника 18
Регулярный многогранник 294
— симплекс 23
Редукция графа 56
Релаксационный многогранник 136
Связное подмножество 94
Связноцелочисленный многогранник 156
Связный граф 53
— подкомплекс 98
Сдвиг множества на вектор 13
Сечение линзы 58
— многогранника 48
Сильная гипотеза Бержа о совершенных графах 140
Сильно отделимые множества 15
Симметрический транспортный многогранник 287
Симплекс 22
Симплекс-таблица 35
Симплексная толщина многогранника 71
Симплициальный комплекс 74
— многогранник 23
Система различных представителей 134
Склейка многогранников по вершинам 67
Смежностная размерность многогранника 204
Смежные вершины графа 53
Собственная грань многогранника 18
Совершенное паросочетание графа 136
— у -сочетание 317
Совершенный граф 138
Спектр многогранников 81, 234
Срез вершины многогранника 76
Стандартная диаграмма Гейла 87
Степень вершины графа 54, 172
— вырожденности вершины 265
Сток орграфа 131
Субмодулярная функция 143
Субстохастическая матрица 189
Сумма многогранников 25
Супермодулярная функция 143
Теорема Балинского 54
— Биркгофа 169
— Вей л я — Минковского 19
— Кенига 130
— о представлении 269, 277
— Понтрягина 78
— Радо 181, 183
— Штейница 55
Тип (г, s) 47
Толщина многогранника 69
Точка локального минимума 260
— отделена (d—1)-гранью d-многогранника 60
— строго отделена (d—1)-гранью многогранника 60
Трансверсальный матроид 149
Транспортная задача с ограниченными пропускными способностями 288
Трехнндексный пленарный транспортный многогранник 298
Тур 175
Турнир 205
Унимодулярная последовательность 319
Унимодуляриое множество 162
Упаковка множества 135
Уравнение Дена—Соммервиля 43, 45
Уравновешенная булева матрица 140
Уравновешенный гиперграф 164
Усеченный транспортный многогранник 267
Условия Моравека — Влаха 301
— Смита 302
— Хели 300
— Шелла 299
Формула Эйлера—Пуанкаре 39
Функция, вогнутая по Шуру 259
Хроматическое число графа 128
Целочисленная решетка 106
— точка 106
Целочисленный базис подпространства 161
— вектор 106
— полиэдр 116
— симплекс-метод 153
Центр (L, Р)-регулярной пары многогранников 232
Центральный многогранник 208, 236
Цепь в графе 53
— посещает грань многогранника 65
Цикл без хорд графа 140
— в графе 53
Циклическая перестановка 176
Циклический многогранник 24
Частичная трансверсаль 149
Четная перестановка 187
Число вершинного покрытия 136
— внешней устойчивости гиперграфа 125 I
— внутренней устойчивости 136
гиперграфа 125
— паросочетаний 136
— реберного покрытия 136
Эквивалентные вершины многогранников 229
— многогранники 80, 229, 230
Элементарная матрица 111
Элементарное преобразование матрицы 223
Элементарные преобразования столбцов матрицы 111
строк матрицы НО
Эрмитова матрица 162
— форма матрицы 119
Эйлеров граф 122
Эйлерова матрица 119
i-сочетание графа 164
d-бипирамида 42
d-полиэдральный граф 52
d-призма 47
d-связный граф 63
d-симплекс 22
d-мерное аффинное множество 14
d-мерное линейное пространство 14
d-фигура Данцига 63
«¦поток в матроиде 166
f-вектор многограннике 8, 39
^-эквивалентные многогранники 39
i-граднент функции 167
f-грань многогранника 18
^-вырожденный многогранник 231
ft-комплекс 74
6-минорная степень матрицы 163
ft-подобные симплекс-таблицы 38
^-приводимая система векторов 292
^-регулярная симплекс-таблица 38
fc-скелет многогранника 74
?-смежностный многогранник 24
(*, О-усеченный транспортный многогранник 274
(L, Р)-вырожденный многогранник 231
(L, Р)-регулярная пара многогранников 231
/-толщина многогранника 70
/л-размещение 188
л-дольный граф 256
л-цикл 95
р-индексный планарный транспортный многогранник 313
р-индексная транспортная задача с максимальными суммами 290
р-индексная m-арная транспортная задача 290
р-куб порядка n 305
г-гранная d-пирамида 84
г-мерное базисное множество многогранника 48
(г, 5)-множество 94
r-симплициальный многогранник 47
s-простой многогранник 47
(t, n, р)-ортогональная система р-кубов порядка n 307
а-критическое ребро графа 163
а-модулярная матрица 117
а-усеченный транспортный многогранник 284
р-замкнутое подмножество 147
р-несепарабельное подмножество 147
р-сепарабельное подмножество 147
(±1)-матрица 119

 

 

 

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

 

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