Интегральный многогранник - Integral polytope

Четыре интегральных многогранника в трех измерениях


Куб	Кубооктаэдр	Октаэдр	Усеченный октаэдр
(±1, ±1, ±1)	(0, ±1, ±1)	(0, 0, ±1)	(0, ±1, ±2)

В геометрии и многогранная комбинаторика, интегральный многогранник это выпуклый многогранник чей вершины у всех есть целое число Декартовы координаты.^[1] То есть это многогранник, равный выпуклый корпус своего целые точки.^[2]Интегральные многогранники также можно назвать выпуклые решетчатые многогранники или же Z-многогранники. Частные случаи двумерных и трехмерных целочисленных многогранников можно назвать многоугольниками или многогранниками вместо многогранников соответственно.

Примеры

An ${ displaystyle n}$ -мерная регулярная симплекс можно представить в виде целочисленного многогранника в ${ Displaystyle mathbb {R} ^ {п + 1}}$ , выпуклая оболочка целых точек, для которых одна координата равна единице, а остальные равны нулю. Другой важный тип интегрального симплекса - орто-схема, может быть сформирована как выпуклая оболочка целых точек, координаты которых начинаются с некоторого количества последовательных единиц, за которыми следуют нули во всех остальных координатах. В ${ displaystyle n}$ -размерный единичный куб в ${ Displaystyle mathbb {R} ^ {п}}$ имеет в качестве вершин все целые точки, координаты которых равны нулю или единице.

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

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

Некоторые многогранники, возникающие из комбинаторная оптимизация проблемы автоматически интегрируются. Например, это верно для порядковый многогранник любой частично заказанный набор, многогранник, определяемый попарными неравенствами между координатами, соответствующими сравнимым элементам в множестве.^[3]

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

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

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

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

Интегральные многогранники занимают видное место в теории торические многообразия, где они соответствуют поляризованным проективным торическим многообразиям, например, торическое многообразие, соответствующее симплекс это проективное пространство. Торическое многообразие, соответствующее единичный куб это Сегре встраивание из ${ displaystyle n}$ -кратное произведение проективной прямой.^{[нужна цитата ]}

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

Рекомендации

^ Корнежоль, Жерар (2001), Комбинаторная оптимизация: упаковка и покрытие, Серия региональных конференций CBMS-NSF по прикладной математике, 74, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM), стр. 4, Дои:10.1137/1.9780898717105, ISBN 0-89871-481-8, МИСТЕР 1828452
^ Мурота, Кадзуо (2003), Дискретный выпуклый анализ, Монографии SIAM по дискретной математике и приложениям, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM), стр. 90, Дои:10.1137/1.9780898718508, HDL:2433/149564, ISBN 0-89871-540-7, МИСТЕР 1997998
^ Стэнли, Ричард П. (1986), "Два многогранника посета", Дискретная и вычислительная геометрия, 1 (1): 9–23, Дои:10.1007 / BF02187680, МИСТЕР 0824105
^ Дин, Гуоли; Фэн, Ли; Занг, Венан (2008), "Сложность распознавания линейных систем с определенными свойствами целостности", Математическое программирование, серия A, 114 (2): 321–334, Дои:10.1007 / s10107-007-0103-y, HDL:10722/58972, МИСТЕР 2393045
^ Барвинок, А. И. (1994), "Вычисление полинома Эрхарта выпуклого решетчатого многогранника", Дискретная и вычислительная геометрия, 12 (1): 35–48, Дои:10.1007 / BF02574364, МИСТЕР 1280575

[c-1] Корнежоль, Жерар (2001), Комбинаторная оптимизация: упаковка и покрытие, Серия региональных конференций CBMS-NSF по прикладной математике, 74, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM), стр. 4, Дои:10.1137/1.9780898717105, ISBN 0-89871-481-8, МИСТЕР 1828452

[m-2] Мурота, Кадзуо (2003), Дискретный выпуклый анализ, Монографии SIAM по дискретной математике и приложениям, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM), стр. 90, Дои:10.1137/1.9780898718508, HDL:2433/149564, ISBN 0-89871-540-7, МИСТЕР 1997998

[s-3] Стэнли, Ричард П. (1986), "Два многогранника посета", Дискретная и вычислительная геометрия, 1 (1): 9–23, Дои:10.1007 / BF02187680, МИСТЕР 0824105

[dfz-4] Дин, Гуоли; Фэн, Ли; Занг, Венан (2008), "Сложность распознавания линейных систем с определенными свойствами целостности", Математическое программирование, серия A, 114 (2): 321–334, Дои:10.1007 / s10107-007-0103-y, HDL:10722/58972, МИСТЕР 2393045

[b-5] Барвинок, А. И. (1994), "Вычисление полинома Эрхарта выпуклого решетчатого многогранника", Дискретная и вычислительная геометрия, 12 (1): 35–48, Дои:10.1007 / BF02574364, МИСТЕР 1280575

[1]

[2]

[3]

[4]

[5]