Cтраница 1
Свойства многогранников изучал Эйлер, ему принадлежит теорема, устанавливающая зависимость между числом граней ( Г), вершин ( В) и ребер ( Р) выпуклых многогранников всех видов. [1]
Особенность данной монографии состоит в изучении комбинаторных свойств многогранников ( множеств решений систем линейных неравенств) в тесной связи с задачами оптимизации, которые важны для практических применений. [2]
Наряду с соотношениями Дена-Соммервилля ( 24) ряд других комбинаторных свойств простых многогранников получают красивую интерпретацию в терминах многообразий Zp. В частности, соотношение ( 27) позволяет записать известные неравенства Мак Мюллена, верхнюю и нижнюю оценки для числа граней простого многогранника ( см. [3]) в терминах когомологий многообразия Zp. [3]
Выбор одного из этих способов или их комбинации зависит от свойств данных многогранников. Построения будут более простыми, если вершины ломаной определяются для проецирующих ребер, а стороны ломаной - для проецирующих граней. При выборе вспомогательных плоскостей для построения вершин и сторон ломаной с участием ребер и граней общего положения необходимо руководствоваться рекомендациями, сформулированными в пп. [4]
В частности, изучены зависимости между многоиндексными задачами о назначениях и ортогональными системами латинских кубов. Тем самым обнаружена связь между свойствами многогранников и конечных геометрий ( § 3 гл. [5]
Симплексный метод является одним из эффективных методов решения задач оптимизации высокой размерности. Алгоритм этого метода основан на использовании некоторых свойств простейших многогранников / г-мерного пространства симплексов. [6]
Симплексный метод является одним из эффективных методов решения задач оптимизации высокой размерности. Алгоритм этого метода основан на использовании некоторых свойств простейших многогранников я-мерного пространства симплексов. [7]
Типичные для комбинаторной геометрии задачи связаны с оценкой числа фигур, входящих в удовлетворяющую условиям задачи конфигурацию. Большинство задач комбинаторной геометрии ставится для выпуклых тел, в связи с чем при решении многих из них используются свойства многогранников. Последнее стимулировало исследование комбинаторных и метрических свойств многогранников и зависимостей между ними. Это привело в начале 50 - х годов к возникновению и выдвижению на первое место нового раздела теории выпуклых многогранников - комбинаторной теории многогранников. [8]
Типичные для комбинаторной геометрии задачи связаны с оценкой числа фигур, входящих в удовлетворяющую условиям задачи конфигурацию. Большинство задач комбинаторной геометрии ставится для выпуклых тел, в связи с чем при решении многих из них используются свойства многогранников. Последнее стимулировало исследование комбинаторных и метрических свойств многогранников и зависимостей между ними. Это привело в начале 50 - х годов к возникновению и выдвижению на первое место нового раздела теории выпуклых многогранников - комбинаторной теории многогранников. [9]
Под n - мерным выпуклым многогранником мы понимаем произвольное ограниченное множество в Мп, задаваемое как пересечение конечного числа полупространств. Любой выпуклый многогранник ограничивается конечным числом гиперплоскостей. Таким образом, гиперплоскости, ограничивающие простой многогранник, находятся в общем положении. При этом если множество точек находится в общем положении, то получаемый многогранник называется симплициальным, так как все его грани будут симплексами. Часто бывает удобно исследовать свойства простого многогранника в терминах двойственного ему симплициального многогранника, а также симплициального разбиения сферы, задаваемого границей этого двойственного многогранника. [10]
Четвертая проблема комбинаторной теории многогранников охватывает комплекс задач, связанный с поиском эффективного способа перехода от одной формы задания многогранника к другой. Для перехода от аналитической формы задания к параметрической необходимо найти все вершины многогранника. В некоторых случаях это удается сделать в явном виде, но чаще изучаются только свойства вершин. Особенно важно бывает установить целочисленность координат всех вершин многогранника; такие многогранники называются целочисленными. Целочисленные многогранники играют фундаментальную роль в целочисленном программировании. Задача описания всех систем линейных неравенств, задающих целочисленные многогранники, не решена. Однако уже вскрыта глубокая связь между целочисленными многогранниками и многими важными проблемами теории графов и гиперграфов, такими, как сильная гипотеза Бержа о совершенных графах ( § 5 гл. Любой результат, касающийся целочисленных многогранников, автоматически влечет серию результатов в теории графов. IV практически все наиболее важные теоремы о покрытиях и паросочета-ниях в графах, такие, как теорема Кенига, Уитни, Менгера, Гейла и др. выводятся из свойств целочисленных многогранников. Многие ставшие хорошо известными теоремы о матроидах и полиматроидах также выводятся из свойства целочисленности соответствующих многогранников. IV понятие а-модулярных матриц дает возможность расширить известные ранее классы целочисленных многогранников. IV предпринимается систематическое изучение также классов многогранников, у которых часть вершин с целыми координатами обладает определенными свойствами, позволяющими решать задачи целочисленного программирования алгоритмами симплексного типа. Среди таких многогранников оказались такие важные для приложений задачи, как задача о / 7-медиане, об упаковке ребер гиперграфа, о размещении. [11]