Целочисленный многогранник

Куб	Кубооктаэдр	Октаэдр	Усечено октаэдр
(±1, ±1, ±1)	(0, ±1, ±1)	(0, 0, ±1)	(0, ±1, ±2)
Четыре целых многогранника в трех измерениях

В геометрии и многогранной комбинаторике целым многогранником называется выпуклый многогранник которого вершины , все имеют целые декартовы координаты . То есть это многогранник, равный выпуклой оболочке его целых точек . Целочисленные многогранники также называются решетчатыми многогранниками или Z-многогранниками . Частные случаи двумерных и трехмерных целочисленных многогранников можно называть многоугольниками или многогранниками вместо многогранников соответственно.

Примеры

Ан $n$-мерный правильный симплекс можно представить в виде целочисленного многогранника в $\mathbb {R} ^{n+1}$, выпуклая оболочка целочисленных точек, для которых одна координата равна единице, а остальные равны нулю. Другой важный тип целочисленного симплекса, ортосхема , может быть сформирован как выпуклая оболочка целых точек, координаты которых начинаются с некоторого количества последовательных единиц, за которыми следуют нули во всех остальных координатах. $n$-мерный единичный куб в $\mathbb {R} ^{n}$ имеет вершинами все целые точки, координаты которых равны нулю или единице. Пермутаэдр имеет вершины , координаты которых получены применением всех возможных перестановок к вектору $(1,2,...,n)$. Ассоциэдр в выпуклой реализации Лодея также является целочисленным многогранником и деформацией пермутаэдра.

В оптимизации

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

Некоторые многогранники, возникающие в результате задач комбинаторной оптимизации, автоматически являются целыми. Например, это верно для порядкового многогранника любого частично упорядоченного множества , многогранника, определяемого парными неравенствами между координатами, соответствующими сравнимым элементам в наборе. Еще один известный многогранник в комбинаторной оптимизации — это совпадающий многогранник . Очевидно, что поиск паросочетаний осуществляется алгоритмически, и одним из методов является линейное программирование. Многогранник, описываемый линейной программой, ограничивающей сверху сумму ребер, взятых на одну вершину, является целым в случае двудольных графов , то есть в точности описывает соответствующий многогранник, тогда как для общих графов он нецелочислен. Следовательно, для двудольных графов достаточно решить соответствующую линейную программу, чтобы получить допустимое паросочетание . Однако для общих графов существуют две другие характеристики соответствующего многогранника, одна из которых использует неравенство Блума для нечетных подмножеств вершин и, следовательно, позволяет преобразовать целочисленную программу в линейную, сохраняя при этом действительные сопоставления. Эти характеристики представляют дополнительный интерес для знаменитого алгоритма Блума Эдмондса, используемого для поиска таких паросочетаний в общих графах.

Вычислительная сложность

Для многогранника, описываемого линейными неравенствами, если многогранник нецелый, его нецелостность можно доказать, найдя вершину, координаты которой не являются целыми числами. Такую вершину можно описать комбинаторно, задав подмножество неравенств, которые при преобразовании в систему линейных уравнений имеют единственное решение, и проверив, что эта точка решения подчиняется всем остальным неравенствам. Таким образом, проверка целостности относится к классу сложности задач coNP , для которых можно легко доказать отрицательный ответ. Точнее, он coNP-полный .

Связанные объекты

Многие важные свойства целочисленного многогранника, включая его объем и количество вершин, кодируются его полиномом Эрхарта .

Целочисленные многогранники занимают видное место в теории торических многообразий , где они соответствуют поляризованным проективным торическим многообразиям.Например, торическое многообразие, соответствующее симплексу, является проективным пространством . Торическое многообразие, соответствующее единичному кубу, представляет собой вложение Сегре $n$ -кратное произведение проективной прямой.

В алгебраической геометрии важным примером решетчатых многогранников, называемых многогранниками Ньютона, являются выпуклые оболочки векторов, представляющих показатели степени каждой переменной в терминах многочлена . Например, полином $xy+2x^{2}+y^{5}+4$ имеет четыре члена, $xy$ с вектором экспоненты (1,1), $2x^{2}$ с вектором показателя (2,0), $y^{5}$ с вектором показателя (0,5) и $4$ с вектором показателя (0,0). Его многогранник Ньютона представляет собой выпуклую оболочку четырех точек (1,1), (2,0), (0,5) и (0,0). Эта оболочка представляет собой цельный треугольник с точкой (1,1) внутри треугольника и тремя другими точками в качестве его вершин.

См. также

• Рив тетраэдр