Читать онлайн «Многогранники, графы, оптимизация»

в. А. ЕМЕЛИЧЕВ, М. М. КОВАЛЕВ, М. К. КРАВЦОВ МНОГОГРАННИКИ ГРАФЫ ОПТИМИЗАЦИЯ МОСКВА «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1981 22. 19 ЕвО УДК 519. 6 Многогранники, графы, оптимизация (комбинаторная теория мвогогран- ников). Емеличев В. А. , Ковалев М. М. , Кравцов М. К. — М. : Наука. Главная редакция физико-математической литературы, 1981. — 344 с. Книга посвящена комбинаторной теории многогранников. Наряду с классическими результатами представлена новая проблематика, порожденная задачами оптимизации. Устанавливаются и исследуются связи многогранников с графами и проективными геометриями, излагаются способы построения выпуклых оболочек допустимых областей в задачах целочисленного программирования. Детально изложены результаты о многогранниках транспортной задачи. Рассмотрены проблемы полиэдральной комбинаторики, связанные с задачами оптимизации иа матроидах и полиматрондах. onoru 117 © И»дательстж) «Наука». I. Выпуклые многогранники 13 § 1. Выпуклые множества 13 I 2. Выпуклые многогранники 18 § 3. Операции над многогранниками •. 25 I 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 I 3. Абсолютно унимодулярные матрицы 119 1 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 1. Основные определения и свойства 209 § 2. Базисы и остовные деревья 212 1* 3 3. грани 215 4. Диаметр > . . . 218 5. Многогранники с минимальным числом вершин 227 е. Основные понятия 229 7. Многогранн;1ки с максимальным числом вершин 236 § 8. Подсчет числа ф(т, я) 244 § 9. Минимальное число вершин в классе невырожденных транспортных многогранников с заданным числом граней 249 § 10. Асимптотика 252 Задачи и дополнения 255 Глава VII. Транспортные многогранники с дополнительными усло- впямн 267 § 1. Усечэдные транспортные многогранники , 267 § 2. (к, <)-усеченные транспортные многогранники , • • . 274 $ 3. Распределительный многогранник ... i. >. . > 280 Задачи и дополнения ... . ,,. . 283 Глава VIII.