Многогранник Кли

Многогранник Кли — конструкция позволяющая получить новый многогранник по данному. Названа в честь американского математика Виктора Кли

Описание

Пусть P — выпуклый многогранник в пространстве любой размерности. Тогда многогранник Кли P^K многогранника P образован добавлением к каждой грани P невысокой пирамиды с основанием в этой грани.

Замечания

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

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

Примеры

Триакистетраэдр является многогранником Кли тетраэдра, триакисоктаэдр является многогранником Кли октаэдра, а триакисикосаэдр является многогранником Кли икосаэдра. Во всех этих случаях многогранник Кли образован добавлением треугольной пирамиды к каждой грани исходного многогранника. Конвей использовал для такой операции введённый Кеплером префикс kis (оператор kis Конвея), что можно заметить в названиях многогранников Кли.

Многогранники Кли правильных многогранников

Триакистетраэдр многогранник Кли тетраэдра.

Тетракисгексаэдр многогранник Кли куба.

Триакисикосаэдр многогранник Кли октаэдра.

Пентакисдодекаэдр многогранник Кли додекаэдра.

Триакисикосаэдр многогранник Кли икосаэдра.

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

Некоторые другие многогранники Кли

Гекзакисоктаэдр многогранник Кли ромбододекаэдра.

Гекзакисикосаэдр многогранник Кли ромботриаконтаэдра.

Трипентакисикосододекаэдр многогранник Кли икосододекаэдра.

Базовый многогранник для многогранника Кли не обязан быть правильным. Например, гекзакисоктаэдр является многогранником Кли ромбододекаэдра, образованным заменой каждой ромбической грани додекаэдра ромбической пирамидой, а гекзакисикосаэдр является многогранником Кли ромботриаконтаэдра. Фактически, базовый многогранник не обязан быть гранетранзитивным телом, как видно на примере трипентакисикосододекаэдра выше.

Граф Голднера–Харари может быть представлен как граф вершин и рёбер многогранника Кли треугольной бипирамиды.

Некоторые невыпуклые многогранники Кли на базе тел Кеплера — Пуансо

Малый звёздчатый пентакисдодекаэдр многогранник Кли малого звёздчатого додекаэдра.

Большой звёздчатый пентакисдодекаэдр многогранник Кли большого звёздчатого додекаэдра.

Большой пентакисдодекаэдр многогранник Кли большого додекаэдра.

Большой триакисикосаэдр многогранник Кли большого икосаэдра.

Свойства и приложения

Если P имеет достаточно вершин относительно его размерности, то многогранник Кли многогранника P недвусмысленен относительно размерности — граф, образованный его рёбрами и вершинами, не является графом другого многогранника в другой размерности. Конкретнее, если число вершин d-мерного многогранника P не меньше d²/2, то P^K недвусмысленен относительно размерности.

Если любая i-размерная фасета d-размерного многогранника P является симплексом, и если i ≤ d − 2, то любая (i + 1)-размерная фасета P^K также является симплексом. В частности, многогранник Кли любого трёхмерного многогранника является симплициальным многогранником, многогранником, у которого все грани являются треугольниками.

Многогранник Кли можно использовать для генерации многогранников, не содержащих каких-либо гамильтоновых циклов — любой путь через одну из вершин, добавленных при построении многогранника Кли, должен войти в вершину и выйти из неё через её соседей, принадлежащих исходному многограннику, и если новых вершин будет больше, чем вершин исходного многогранника, то не будет достаточного числа вершин, чтобы путь существовал. В частности, граф Голднера–Харари, многогранник Кли треугольной бипирамиды, имеет шесть вершин, добавленных при построении многогранника Кли, и только пять вершин в бипирамиде, из которой многогранник Кли был создан, так что граф не является гамильтоновым. Это самый простой негамильтонов симплициальный многогранник. Если многогранник с n вершинами образован многократным построением многогранника Кли, начиная с тетраэдра, то его самый длинный путь имеет длину O(n^{log₃ 2}). То есть показатель короткости этих графов равен log₃ 2, примерно 0.630930. Та же техника показывает, что в любой более высокой размерности d существуют симплициальные многогранники с показателем близости log_d 2. Пламмер использовал построение многогранника Кли для создания бесконечного семейства примеров симплициальных многогранников с чётным числом вершин, не имеющих совершенных паросочетаний.

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

Литература

• Stanislav Jendro'l, Tomáš Madaras. Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs // Tatra Mountains Mathematical Publications. — 2005. — Т. 30. — С. 149–153.
• A. Goldner, F. Harary. Note on a smallest nonhamiltonian maximal planar graph // Bull. Malaysian Math. Soc.. — 1975. — Т. 6, вып. 1. — С. 41–42.. См. также тот же журнал 6(2):33 (1975) и 8:104-106 (1977). Ссылки из статьи Харари.
• Branko Grünbaum. Unambiguous polyhedral graphs // Israel Journal of Mathematics. — 1963. — Т. 1, вып. 4. — С. 235–238. — doi:10.1007/BF02759726.
• Branko Grünbaum. Convex Polytopes. — Wiley Interscience, 1967.
• J. W. Moon, L. Moser. Simple paths on polyhedra // Pacific Journal of Mathematics. — 1963. — Т. 13. — С. 629–631. — doi:10.2140/pjm.1963.13.629.
• Michael D. Plummer. Extending matchings in planar graphs IV // Discrete Mathematics. — 1992. — Т. 109, вып. 1–3. — С. 207–219. — doi:10.1016/0012-365X(92)90292-N.