Комбинаторика многогранников

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

Исследования в комбинаторике многогранников распадаются на две ветви. Математики, работающие в этой области, изучают комбинаторику многогранников; например, они ищут неравенства, описывающие отношения между числом вершин, рёбер и граней разных размерностей в произвольном многограннике, а также изучают другие комбинаторные свойства многогранников, такие как связность и диаметр (число шагов, необходимых для достижения любой вершины из любой другой вершины). Кроме того, многие учёные, работающие в области информатики, используют фразу «комбинаторика многогранников» для описания исследований по точному описанию граней некоторых определённых многогранников (особенно, 0-1 многогранников, вершины которых являются подмножествами гиперкуба), возникающих из задач целочисленного программирования.

Грани и вектора подсчёта граней

Решётка граней выпуклого многогранника.

Грань выпуклого многогранника P можно определить как пересечение P и замкнутого полупространства H, такого, что граница H не содержит внутренних точек P. Размерность грани равна размерности этого пересечения. 0-мерные грани — это сами вершины, а 1-мерные грани (называются рёбрами) являются отрезками, соединяющими пары вершин. Заметим, что это определение включает в качестве граней пустые множества и весь многогранник P. Если P имеет размерность d, грани P с размерностью d − 1 называются фасками многогранника P, а грани размерности d − 2 называются гребнями[1]. Грани P могут быть частично упорядочены по включению, образуя решётку граней, имеющую на вершине сам многогранник P и пустое множество внизу.

Ключевым методом комбинаторики многогранников является рассмотрение ƒ-вектора многогранника[2] — вектора (f0, f1, …, fd − 1), где fi является числом i-мерных граней многогранника. Например, куб имеет восемь вершин, двенадцать рёбер и шесть граней (фасок), так что его ƒ-вектор равен (8,12,6). Двойственный многогранник имеет ƒ-вектор с тем же числами в обратном порядке. Так, например, правильный октаэдр, двойственный кубу, имеет ƒ-вектор (6,12,8). Расширенный ƒ-вектор образуется добавлением единиц к обоим концам ƒ-вектора, что соответствует перечислению объектов всех уровней решётки граней: f−1 = 1 отражает пустое множество в качестве грани, в то время как fd = 1 отражает сам P. Для куба расширенный ƒ-вектор — это (1,8,12,6,1), а для октаэдра — (1,6,12,8,1). Хотя вектора этих примеров унимодальны[англ.] (элементы слева направо сначала возрастают, а затем убывают), существуют многогранники более высоких размерностей, для которых это неверно[3].

Для симплициальных политопов (политопов, у которых каждая грань является симплексом) часто преобразуют этот вектор, образуя h-вектор. Если мы рассматриваем элементы ƒ-вектора (без конечной 1) как коэффициенты многочлена ƒ(x) = Σfixd − i − 1 (например, для октаэдра это даёт многочлен ƒ(x) = x3 + 6x2 + 12x + 8), тогда h-вектор содержит коэффициенты многочлена h(x) = ƒ(x − 1) (опять, для октаэдра, h(x) = x3 + 3x2 + 3x + 1)[4]. Как пишет Циглер, «для различных задач о симплициальных политопах h-вектора много более удобны для задания информации о числе граней, чем f-вектора.»

Равенства и неравенства

Наиболее важное соотношение коэффициентов ƒ-вектора многогранника — это формула Эйлера Σ(−1)ifi = 0, где суммирование ведётся по элементам расширенного ƒ-вектора. В трёхмерном пространстве перенос двух единиц с левой и правой стороны расширенного ƒ-вектора (1, v, e, f, 1) в правую сторону равенства преобразует равенство к более привычному виду v − e + f = 2. Из того факта, что любая грань трёхмерного многогранника имеет по меньшей мере три ребра, следует, что 2e ≥ 3f . Используя это выражение для исключения e и f из формулы Эйлера, получим e ≤ 3v − 6 и f ≤ 2v − 4. Ввиду двойственности e ≤ 3f − 6 и v ≤ 2f − 4. Из теоремы Штайница следует, что любой 3-мерный целочисленный вектор, удовлетворяющий этим равенствам и неравенствам, является ƒ-вектором выпуклого многогранника[5].

В более высоких размерностях становятся важными и другие отношения между числом граней многогранника, включая уравнение Дена — Сомервиля, которое, выраженное в терминах h-векторов симплициальных политопов, принимает простую форму hk = hd − k для любого k. Вариант этих уравнений с k = 0 эквивалентен формуле Эйлера, но для d > 3 эти уравнения линейно независимы друг от друга и накладывают дополнительные ограничения на h-вектора (а потому и на ƒ-вектора)[4].

Ещё одно важное неравенство для числа граней многогранника получается из теоремы о верхней оценке[англ.], впервые доказанной МакМалленом[6], которая утверждает, что d-мерный многогранник с n вершинами может иметь не больше граней какой-либо размерности, чем смежностный многогранник с тем же числом вершин:

[math]\displaystyle{ f_{k-1} \le \sum_{i=0}^{d/2} {}^* \left( \binom{d-i}{k-i}+\binom{i}{k-d+i} \right) \binom{n-d-1+i}{i}, }[/math]

где звёздочка означает, что последний член суммы должен быть уменьшен вдвое, если d чётно[7]. В асимптоте из этого следует, что не может быть более чем [math]\displaystyle{ \scriptstyle O(n^{\lfloor d/2\rfloor}) }[/math] граней всех размерностей.

Даже для размерности четыре множество всех возможных ƒ-векторов выпуклых многогранников не образует выпуклое подмножество четырёхмерной целочисленной решётки и много остаётся неясным о возможных значениях этих векторов[8].

Свойства из теории графов

Наряду с числом граней многогранников исследователи изучают и другие их комбинаторные свойства, такие как свойства графов, получаемых из вершин и рёбер многогранников (их 1-скелета[англ.]).

Теорема Балинского утверждает, что граф, полученный таким путём из любого d-мерного выпуклого многогранника, является вершинно d-связным[9][10]. В случае трёхмерных многогранников это свойство и планарность может быть использовано для точного описания графов многогранников — теорема Штайница утверждает, что G является скелетом трёхмерного многогранника тогда и только тогда, когда G является вершинно 3-связным планарным графом[11].

Теорема Блайнда и Мани-Левицка[12] (сформулированная как гипотеза Михой Перле (Micha Perles)) утверждает, что можно восстановить структуру граней простого многогранника по его графу. То есть, если данный неориентированный граф является скелетом простого многогранника, имеется только один многогранник (с точностью до комбинаторной эквивалентности), для которого граф служит скелетом. Это свойство находится в резком контрасте со свойствами смежностных (не простых) многогранников, графы которых являются полными — может существовать много различных смежностных многогранников с одним и тем же графом. Другое доказательство этой теоремы дал Калаи[13], а Фридман [14] показал, как использовать эту теорему для создания алгоритма с полиномиальным временем для построения простых многогранников по их графам.

В контексте симплекс-метода линейного программирования важно учитывать диаметр многогранника, минимальное число вершин, которые необходимо пройти, чтобы достичь любую вершину из любой другой вершины. Система линейных неравенств задачи линейного программирования определяет грани многогранника допустимых решений задачи и симплекс-метод находит оптимальное решение, проходя путь по рёбрам этого многогранника. Таким образом, диаметр оценивает нижнюю границу[англ.] числа шагов этого метода. Опровергнутая гипотеза Хирша давала сильную верхнюю оценку на диаметр[15]. Известна более слабая (квазиполиномиальная) верхняя оценка диаметра[16], а гипотеза Хирша доказана для отдельных классов многогранников[17].

Вычислительные свойства

Определение того, ограничено ли число вершин заданного многогранника некоторым натуральным числом k, является трудной задачей и принадлежит классу сложности PP[18].

Грани 0-1 многогранников

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

В качестве примера возьмём многогранник Биркгофа, множество n × n матриц, которые можно образовать выпуклыми комбинациями матриц перестановок. Равным образом, вершины этого многогранника можно понимать как описание всех совершенных паросочетаний полного двудольного графа, а задачу линейной оптимизации на этом многограннике можно рассматривать как задачу поиска взвешенного минимального совершенного паросочетания. Теорема Биркгофа утверждает, что такой многогранник можно описать с помощью двух типов линейных неравенств. Во-первых, каждый элемент матрицы неотрицателен, во-вторых, для каждого столбца и для каждой строки сумма элементов матрицы равна единице. Ограничения на сумму по строкам и столбцам определяют линейное подпространство размерности n2 − 2n + 1, в котором лежит многогранник Биркгофа, а ограничения на неотрицательность элементов матрицы задают грани многогранника в этом подпространстве.

Многогранник Биркгофа необычен в том, что известно полное описание его граней. Для множества других 0-1 многогранников существует экспоненциально (или суперэкспоненционально) много граней и только частичное их описание доступно[19].

См. также

Примечания

  1. ↑ Ziegler, 1995, с. 51.
  2. ↑ Ziegler, 1995, с. 245–246.
  3. ↑ Ziegler, 1995, с. 272.
  4. ↑ 4,0 4,1 Ziegler, 1995, с. 246–253.
  5. ↑ Steinitz, 1906.
  6. ↑ McMullen, 1970.
  7. ↑ Ziegler, 1995, с. 254–258.
  8. ↑ Höppner, Ziegler, 2000.
  9. ↑ Balinski, 1961.
  10. ↑ Ziegler, 1995, с. 95–96.
  11. ↑ Ziegler, 1995, с. 103–126.
  12. ↑ Blind, Mani-Levitska, 1987.
  13. ↑ Kalai, 1988.
  14. ↑ Friedman, 2009.
  15. ↑ Santos, 2012.
  16. ↑ Kalai, Kleitman, 1992.
  17. ↑ Naddef (1989).
  18. ↑ Haase, Kiefer, 2015, с. Thm. 5.
  19. ↑ Ziegler, 2000.

Литература

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Комбинаторика_многогранников&oldid=5812484