Оглавление
Интегральный многогранник
-
Определение интегрального многогранника
- Интегральный многогранник – выпуклый многогранник с целочисленными координатами.
- Также известен как решетчатый многогранник или Z-многогранник.
-
Примеры интегральных многогранников
- n-мерный правильный симплекс в Rn+1.
- Ортосхема – выпуклая оболочка из целых точек с последовательными единицами.
- n-единичный куб в Rn с координатами 0 или 1.
- Пермутаэдр и ассоциаэдр – примеры целочисленных многогранников.
-
Применение в оптимизации
- В линейном программировании целостные многогранники упрощают решение задач целочисленного программирования.
- Некоторые многогранники в комбинаторной оптимизации автоматически становятся целочисленными.
- Для двудольных графов линейное программирование позволяет найти допустимые соответствия.
-
Вычислительная сложность проверки целостности
- Проверка целостности многогранника относится к классу задач coNP.
- Доказательство нецелочисленности многогранника возможно комбинаторным путем.
-
Связанные объекты и теории
- Многочлен Эрхарта кодирует важные свойства интегрального многогранника.
- Интегральные многогранники играют ключевую роль в теории торических многообразий.
- Многогранники Ньютона в алгебраической геометрии представляют собой выпуклые оболочки векторов.
Полный текст статьи: