Многогранник КлиМногогранник Кли — конструкция позволяющая получить новый многогранник по данному. Названа в честь американского математика Виктора Кли[1] ОписаниеПусть P — выпуклый многогранник в пространстве любой размерности. Тогда многогранник Кли PK многогранника P образован добавлением к каждой грани P невысокой пирамиды с основанием в этой грани[2][3]. Замечания
ПримерыТриакистетраэдр является многогранником Кли тетраэдра, триакисоктаэдр является многогранником Кли октаэдра, а триакисикосаэдр является многогранником Кли икосаэдра. Во всех этих случаях многогранник Кли образован добавлением треугольной пирамиды к каждой грани исходного многогранника. Конвей использовал для такой операции введённый Кеплером префикс kis (оператор kis Конвея[англ.]), что можно заметить в названиях многогранников Кли.
Тетракисгексаэдр является многогранником Кли куба, образованным добавлением квадратных пирамид к каждой грани, а пентакисдодекаэдр является многогранником Кли додекаэдра, образованный добавлением пятиугольных пирамид.
Базовый многогранник для многогранника Кли не обязан быть правильным. Например, гекзакисоктаэдр является многогранником Кли ромбододекаэдра, образованным заменой каждой ромбической грани додекаэдра ромбической пирамидой, а гекзакисикосаэдр является многогранником Кли ромботриаконтаэдра. Фактически, базовый многогранник не обязан быть гранетранзитивным телом, как видно на примере трипентакисикосододекаэдра выше. Граф Голднера–Харари может быть представлен как граф вершин и рёбер многогранника Кли треугольной бипирамиды.
Свойства и приложенияЕсли P имеет достаточно вершин относительно его размерности, то многогранник Кли многогранника P недвусмысленен относительно размерности — граф, образованный его рёбрами и вершинами, не является графом другого многогранника в другой размерности. Конкретнее, если число вершин d-мерного многогранника P не меньше d2/2, то PK недвусмысленен относительно размерности[2][5]. Если любая i-размерная фасета d-размерного многогранника P является симплексом, и если i ≤ d − 2, то любая (i + 1)-размерная фасета PK также является симплексом. В частности, многогранник Кли любого трёхмерного многогранника является симплициальным многогранником, многогранником, у которого все грани являются треугольниками. Многогранник Кли можно использовать для генерации многогранников, не содержащих каких-либо гамильтоновых циклов — любой путь через одну из вершин, добавленных при построении многогранника Кли, должен войти в вершину и выйти из неё через её соседей, принадлежащих исходному многограннику, и если новых вершин будет больше, чем вершин исходного многогранника, то не будет достаточного числа вершин, чтобы путь существовал. В частности, граф Голднера–Харари, многогранник Кли треугольной бипирамиды, имеет шесть вершин, добавленных при построении многогранника Кли, и только пять вершин в бипирамиде, из которой многогранник Кли был создан, так что граф не является гамильтоновым. Это самый простой негамильтонов симплициальный многогранник[6][7]. Если многогранник с n вершинами образован многократным построением многогранника Кли, начиная с тетраэдра, то его самый длинный путь имеет длину O(nlog3 2). То есть показатель короткости этих графов равен log3 2, примерно 0.630930. Та же техника показывает, что в любой более высокой размерности d существуют симплициальные многогранники с показателем близости logd 2[8]. Пламмер[9] использовал построение многогранника Кли для создания бесконечного семейства примеров симплициальных многогранников с чётным числом вершин, не имеющих совершенных паросочетаний. Многогранники Кли имеют некоторые экстремальные свойства, связанные с их степенями вершин — если любое ребро в планарном графе инцидентно по меньшей мере семи другим рёбрам, то должна существовать вершина степени, не превосходящей пяти, но одна из её соседей будет иметь степень 20 или больше. Многогранник Кли многогранника Кли икосаэдра даёт пример, в котором степень вершин с высокой степенью равна в точности 20[10]. Примечания
Литература
|
Portal di Ensiklopedia Dunia
