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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
3-мерный выпуклый многогранник

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

Иногда термин «многогранник» используется для обозначения выпуклого многогранника.

Определения[править | править вики-текст]

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

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

Связанные определения[править | править вики-текст]

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

Примеры[править | править вики-текст]

Свойства[править | править вики-текст]

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

Вариации и обобщения[править | править вики-текст]

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

  1. Glen Bredon[en]. Topology and Geometry. — 1993. — ISBN 0-387-97926-3, p. 56..
  2. Hassler Whitney Congruent graphs and the connectivity of graphs // Amer. J. Math.. — 1932. — Т. 54, вып. 1. — С. 150–168.
  3. Volker Kaibel, Alexander Schwartz {{{заглавие}}} // Graphs and Combinatorics. — 2003. — Т. 19, вып. 2. — С. 215–230.
  4. 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..

Внешние ссылки[править | править вики-текст]