WikiSort.ru - Не сортированное

Многогранник Кли выпуклого многогранника P в пространстве любой размерности — это другой многогранник P^K, образованный заменой каждой фасеты многогранника P невысокой пирамидой^[1][2]. Многогранники названы по имени американского математика Виктора Кли^[en] (Victor Klee)^[3]

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определения

Один из методов формирования многогранника Кли многогранника P заключается в помещении новой вершины вне P рядом с центром каждой фасеты. Если все эти новые вершины поместить достаточно близко к соответствующим центрам, то только вершины фасеты, на которой определена новая вершина, будут видны из неё. В этом случае многогранником Кли P будет выпуклая оболочка объединения вершин P и набора новых вершин^[4].

Альтернативно, многогранник Кли можно определить с помощью двойственности и двойственной ей операции, усечения — многогранник Кли многогранника P является двойственным многогранником усечения двойственного P многогранника.

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

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

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

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

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

Примечания

Литература

• 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.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.