Интегральный многогранник - Integral polytope
|
|
|
|
|
|
|
|
| Куб | Кубооктаэдр | Октаэдр |
Усеченный октаэдр |
| (± 1, ± 1, ± 1) | (0, ± 1, ± 1) | (0, 0, ± 1) | (0, ± 1, ± 2) |
| Четыре интегральных многогранника в трех измерениях | |||
|---|---|---|---|
В геометрии и многогранных комбинаторики , интеграл многогранник является выпуклый многогранник , чьи вершины всех есть целое число декартовых координат . То есть это многогранник, равный выпуклой оболочке своих целых точек . Целочисленные многогранники можно также называть многогранниками выпуклой решетки или Z-многогранниками . Частные случаи двух- и трехмерных целочисленных многогранников можно называть многоугольниками или многогранниками вместо многогранников соответственно.
Примеры
-Мерном регулярный симплекс можно представить как целое многогранника , выпуклая оболочка целых точек , для которых одна координата один , а остальные равны нулю. Другой важный тип интегрального симплекса, ортосхема , может быть сформирован как выпуклая оболочка целых точек, координаты которых начинаются с некоторого числа последовательных единиц, за которыми следуют нули во всех остальных координатах. - Мерный единичный куб в имеет в качестве своих вершин всех целых точек, координаты которых равна нуль или один.
В оптимизации
В контексте линейного программирования и связанных с ним задач математической оптимизации выпуклые многогранники часто описываются системой линейных неравенств, которым должны подчиняться их точки. Когда многогранник является целым, линейное программирование может использоваться для решения задач целочисленного программирования для данной системы неравенств, что в противном случае может быть более трудным.
Некоторые многогранники, возникающие из задач комбинаторной оптимизации , автоматически становятся целочисленными. Например, это верно для многогранника порядка любого частично упорядоченного множества , многогранника, определяемого попарными неравенствами между координатами, соответствующими сравнимым элементам в наборе.
Вычислительная сложность
Для многогранника, описываемого линейными неравенствами, когда многогранник нецелочислен, можно доказать его нецелочисленность, найдя вершину, координаты которой не являются целыми числами. Такую вершину можно описать комбинаторно, указав подмножество неравенств, которые при преобразовании в систему линейных уравнений имеют единственное решение, и убедившись, что эта точка решения подчиняется всем остальным неравенствам. Следовательно, проверка целостности относится к классу сложности задач coNP, для которых отрицательный ответ может быть легко доказан. В частности, он является coNP-полным .
Связанные объекты
Многие важные свойства целочисленного многогранника, включая его объем и количество вершин, кодируются его многочленом Эрхарта .
Целочисленные многогранники занимают важное место в теории торических многообразий , где они соответствуют поляризованным проективным торическим многообразиям. Например, торическое многообразие, соответствующее симплексу, является проективным пространством . Торическое многообразие , соответствующее единичный куб является Сегрой вложения в -кратном произведении проективного прямой.
В алгебраической геометрии важным примером решетчатых многогранников, называемых многогранниками Ньютона, являются выпуклые оболочки векторов, представляющих показатели каждой переменной в терминах полинома . Например, многочлен имеет четыре члена, с вектором экспоненты (1,1), с вектором экспоненты (2,0), с вектором экспоненты (0,5) и с вектором экспоненты (0,0). Его многогранник Ньютона - это выпуклая оболочка четырех точек (1,1), (2,0), (0,5) и (0,0). Эта оболочка представляет собой цельный треугольник с точкой (1,1) внутри треугольника и тремя другими точками в качестве вершин.
