Выпуклый многогранник

3-мерный выпуклый многогранник

Выпуклый многогранник — многогранник, являющийся выпуклым множеством. Это основное понятие в задачах линейного программирования.

Определения

Выпуклый многогранник определяется как выпуклая оболочка конечного числа точек в евклидовом пространстве.

Связанные определения

  • Выпуклый многогранник называется невырожденным или телесным, если он имеет внутренние точки.
  • Гранью выпуклого многогранника является пересечение многогранника полупространством, при котором никакая внутренняя точка многогранника не лежит на границе полупространства.
    • 0-мерные грани называются вершинами,
    • 1-мерные грани называются рёбрами.
  • n-мерный телесный многогранник называется простым, если в каждой его вершине сходится ровно n рёбер.
  • Два многогранника называются комбинаторно изоморфными, если их решётки граней изоморфны.
  • Граф многогранника — граф, образованный его вершинами и рёбрами, все грани больших размерностей игнорируются.
  • Задание многогранника через гиперплоскости граней называется H-представлением.
  • Задание многогранника как выпуклую оболочку его вершин называется V-представлением.

Примеры

Свойства

  • Грани выпуклого многогранника образуют решётку с эйлеровым частичным порядком, которая называется решёткой граней, где частичный порядок определяется принадлежностью граней. Определение грани, данное выше, позволяет как сам многогранник, так и пустое множество считать гранями. Весь многогранник является единственным максимальным элементом решётки, а пустое множество, являясь (−1)-мерной гранью (пустой многогранник), является единственным минимальным элементом многогранника.
  • Как показал Уитни[3], решётка граней трёхмерного многогранника определяется его графом. То же самое верно, если многогранник является простым (Blind & Mani-Levitska (1987), в книге Kalai (1988) дано простое доказательство). Последний факт является инструментом в доказательстве, что с точки зрения вычислительной сложности задача определения, являются ли два выпуклых многогранника комбинаторно изоморфными, эквивалентна задаче определения, являются ли графы изоморфными, даже если ограничиться классами простых или симплексных многогранников.[4]
  • Любой выпуклый многогранник допускает триангуляцию с множеством вершин совпадающим с множеством вершин многогранника.[5]

Вариации и обобщения

См. также

Примечания

  1. https://scientificrussia.ru/articles/new-class-of-polyhedra-discovered Архивная копия от 11 февраля 2017 на Wayback Machine Новый класс геометрических фигур назвали многранником Голдберга
  2. Glen Bredon[англ.]. Topology and Geometry. — 1993. — ISBN 0-387-97926-3, p. 56..
  3. Hassler Whitney. Congruent graphs and the connectivity of graphs // Amer. J. Math.. — 1932. — Т. 54, вып. 1. — С. 150–168. — JSTOR 2371086.
  4. Volker Kaibel, Alexander Schwartz. {{{заглавие}}} // Graphs and Combinatorics. — 2003. — Т. 19, вып. 2. — С. 215–230. Архивировано 21 июля 2015 года.
  5. B. Büeler, A. Enge, K. Fukuda. Exact Volume Computation for Polytopes: A Practical Study. Polytopes — Combinatorics and Computation.. — 2000. — С. 131. — ISBN 978-3-7643-6351-2. — doi:10.1007/978-3-0348-8438-9_6..

Ссылки