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

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

Опис

Нехай P — опуклий многогранник у просторі будь-якої розмірності. Тоді многогранник Клі P^K многогранника P утворений додаванням до кожної грані P невисокої піраміди з основою в цій грані^[2][3].

Зауваження

• Зазвичай під час побудови многогранника Клі нові вершини вибирають поруч із серединою кожної з граней початкового многогранника. У цьому випадку мнгогранник Клі опуклого многогранника можна визначити як опуклу оболонку вершин початкового многогранника та додаткових вершин^[4].

• Многогранник Клі можна також визначити за допомогою двоїстості як двоїстий многогранник зрізання многогранника, двоїстого початковому.

Приклади

Триакістетраедр є многогранником Клі тетраедра, триакісоктаедр — многогранником Клі октаедра, а триакісікосаедр — ікосаедра. У всіх цих випадках многогранник Клі утворено доданням трикутної піраміди до кожної грані початкового многогранника. Конвей використав для такої операції введений Кеплером префікс kis (оператор kis Конвея^[en]), що можна помітити в назвах многогранників Клі.

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

Триакістетраедр — многогранник Клі тетраедра

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

Триакісікосаедр — многогранник Клі октаедра

Пентакісдодекаедр — многогранник Клі додекаедра

Триакісікосаедр — многогранник Клі ікосаедра

Тетракісгексаедр є многогранником Клі куба, утвореним додаванням квадратних пірамід до кожної грані, а пентакісдодекаедр є многогранником Клі додекаедра, утвореним додаванням п'ятикутних пірамід.

Деякі інші многогранники Клі

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

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

Трипентакісікосододекаедр^[en] — многогранник Клі ікосододекаедра

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

Граф Голднера — Харарі можна подати як граф вершин і ребер многогранника Клі трикутної біпіраміди.

Деякі неопуклі многогранники Клі на базі тіл Кеплера — Пуансо

Малий зірчастий пентакісдодекаедр^[en] — многогранник Клі малого зірчастого додекаедра

Великий зірчастий пентакісдодекаедр^[en] — многогранник Клі великого зірчастого додекаедра

Великий пентакісдодекаедр^[en] — многогранник Клі великого додекаедра

Великий триакісікосаедр^[en] — многогранник Клі великого ікосаедра

Властивості та застосування

Якщо P має достатньо вершин відносно його розмірності, то многогранник Клі многогранника P розмірнісно однозначний — граф, утворений його ребрами і вершинами, не є графом іншого многогранника в іншій розмірності. Конкретніше, якщо кількість вершин d-вимірного многогранника P не менша ніж d²/2, то P^K розмірнісно однозначний^[2][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] використав побудову многогранника Клі для створення нескінченного сімейства прикладів симпліційних многогранників із парним числом вершин, що не мають досконалих парувань.

Многогранники Клі мають деякі екстремальні властивості, пов'язані з їхніми степенями вершин — якщо будь-яке ребро в планарному графі інцидентне принаймні семи іншим ребрам, то має існувати вершина степеня, що не перевищує 5, але одна з її сусідів матиме ступінь 20 або більше. Многогранник Клі многогранника Клі ікосаедра дає приклад, у якому степінь вершин з високим степенем дорівнює рівно 20^[10].

Примітки

1. Joseph Malkevitch. People Making a Difference. — American Mathematical Society.
2. Grünbaum, 1963.
3. Grünbaum, 1967.
4. Grünbaum, 1967, с. 217.
5. Grünbaum, 1967, с. 227.
6. Grünbaum, 1967, с. 357.
7. Goldner, Harary, 1975.
8. Moon, Moser, 1963.
9. Plummer, 1992.
10. Jendro'l, Madaras, 2005.

Література

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