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

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

Опис

Нехай 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. Пламмер використав побудову многогранника Клі для створення нескінченного сімейства прикладів симпліційних многогранників із парним числом вершин, що не мають досконалих парувань.

Многогранники Клі мають деякі екстремальні властивості, пов'язані з їхніми степенями вершин — якщо будь-яке ребро в планарному графі інцидентне принаймні семи іншим ребрам, то має існувати вершина степеня, що не перевищує 5, але одна з її сусідів матиме ступінь 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.