Перейти до вмісту

Теорема Штайніца

Матеріал з Вікіпедії — вільної енциклопедії.

Теорема Штайніца — це комбінаторний опис неорієнтованих графів, утворених ребрами й вершинами тривимірного опуклого многогранника — вони точно є (простими) вершинно 3-зв'язними планарними графами (щонайменше з чотирма вершинами)[1][2]. Тобто будь-який опуклий многогранник утворює 3-зв'язний планарний граф, і будь-який 3-зв'язний планарний граф можна подати як опуклий многогранник. З цієї причини 3-зв'язні планарні графи називають також поліедральними.

Теорему названо ім'ям Ернста Штайніца, який опублікував перше доведення цього результату 1916 року[3]. Бранко Ґрюнбаум назвав цю теорему «найважливішим і найглибшим результатом про тривимірні політопи»[2].

Назву «теорема Штайніца» також застосовують до інших результатів Штайніца:

Твердження теореми

[ред. | ред. код]
Висвітлення скелета опуклого багатогранника точковим джерелом світла, близьким до однієї з його граней, дає тінь у вигляді плоскої діаграми Шлегеля.

Неорієнтований граф — це система вершин і ребер, кожне ребро поєднує дві вершини. З будь-якого многогранника можна утворити граф, якщо за вершини графа прийняти вершини многогранника і з'єднати ребром дві вершини графа, якщо відповідні вершини многогранника є кінцевими точками його ребер. Цей граф відомий як одновимірний кістяк многогранника.

Граф є планарним, якщо його вершини можна позначити точками на площині і намалювати на цій площині ребра графа як криві, що з'єднують ці точки, так, щоб жодні два ребра не перетиналися, а точка лежала на кривій, тільки якщо вершина є кінцевою точкою відповідного ребра. За теоремою Фарі можна вважати, що криві, насправді, є відрізками. Граф вершинно 3-зв'язний, якщо після видалення будь-яких двох його вершин будь-яку пару з решти вершин можна з'єднати шляхом.

Теорема Штайніца в одному напрямку (простішому для доведення) стверджує, що граф будь-якого опуклого многогранника є планарним і 3-зв'язним. Як показано на малюнку, планарність можна показати за допомогою діаграми Шлегеля — якщо розмістити точкове джерело світла поблизу однієї з граней багатогранника, а з іншого боку розмістити площину, тіні ребер многогранника утворюють планарний граф, укладений у площину таким чином, що ребра графа представлені відрізками. 3-зв'язність графа многогранника є окремим випадком теореми Балінського, що граф будь-якого k-вимірного опуклого многогранника є k-зв'язним[10].

Твердження в інший, складніший, бік: будь-який планарний 3-зв'язний граф є графом опуклого многогранника.

Посилення та пов'язані результати

[ред. | ред. код]

Можна довести строгіше твердження теореми Штайніца, що будь-який поліедральний граф можна реалізувати як опуклий мнгогогранник із вершинами, що мають цілі координати. Цілі числа, що виходять в оригінальному доведенні, є двічі експоненціальною функцією[en] від числа вершин заданого многогранника. Таким чином, запис цих чисел вимагає експоненціального числа бітів[11]. Однак у подальших дослідженнях знайдено алгоритм візуалізації графів, який вимагає лише O(n) бітів для кожної вершини[12][13]. Можна послабити вимогу, щоб усі координати були цілими та призначити координати так, що x-координати вершин будуть різними цілими числами в інтервалі [0,2n − 4], а інші дві координати будуть дійсними числами з інтервалу [0,1], тоді кожне ребро матиме довжину не меншу від одиниці, тоді як об'єм многогранника буде обмежений O(n)[14].

У будь-якому многограннику, який відповідає даному поліедральному графу , грані є точно циклами в , які не ділять на дві компоненти. Тобто, видалення з циклу, відповідного грані, дає зв'язний підграф (такі цикли називають периферійними). Можна заздалегідь вказати форму будь-якої однієї грані багатогранника — якщо вибрати цикл , який не розділяє графа на частини, і його вершини розташувати у вигляді двовимірного опуклого многокутника , існує поліедральне подання , в якому грань, відповідна , конгруентна [15]. Також завжди є можливість для заданого поліедрального графа і довільного циклу знайти реалізацію, за якої утворює силует реалізації при паралельній проєкції[16].

Теорему про пакування кіл Кебе — Андрєєва — Терстона можна розглядати як інше посилення теореми Штайніца, що будь-який 3-зв'язний планарний граф можна подати у вигляді опуклого многогранника так, що всі його ребра дотикатимуться до однієї й тієї самої одиничної сфери[17]. Загальніше, якщо  — поліедральний граф і  — гладке тривимірне опукле тіло, можна знайти поліедральне подання , в якому всі ребра дотикаються до [18].

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. Günter M. Ziegler. Chapter 4. «Steinitz' Theorem for 3-Polytopes» // Lectures on Polytopes. — 1995. — P. 103. — ISBN 0-387-94365-X.
  2. а б Branko Grünbaum. Convex Polytopes / Volker Kaibel, Victor Klee[en], Günter M. Ziegler[en]. — 2nd edition. — 2003. — P. 466. — ISBN 0-387-40409-0, 978-0-387-40409-7.
  3. Ernst Steinitz. Encyclopädie der mathematischen Wissenschaften. — 1922. — № IIIAB12. Abgeschlossen am 31. August 1916
  4. Mariusz Zynel. The Steinitz theorem and the dimension of a vector space // Formalized Mathematics. — 1996. — Т. 5, вип. 8. — С. 423—428. — CiteSeerX: 10.1.1.79.1707.
  5. David Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap. Quantitative Steinitz's theorems with applications to multifingered grasping // Discrete & Computational Geometry. — 1992. — Т. 7, вип. 1. — С. 295–318. — DOI:10.1007/BF02187843.
  6. Peter Rosenthal. The remarkable theorem of Lévy and Steinitz // American Mathematical Monthly. — 1987. — Т. 94, вип. 4. — С. 342—351.
  7. Wojciech Banaszczyk. Chapter 3.10 The Lévy-Steinitz theorem // Additive subgroups of topological vector spaces. — Berlin : Springer-Verlag, 1991. — Т. 1466. — P. viii 178. — (Lecture Notes inMathematics) — ISBN 3-540-53917-4.
  8. V. M. Kadets, M. I. Kadets. Chapter 6. The Steinitz theorem and B-convexity // Rearrangements of series in Banach spaces. — Translated by Harold H. McFaden from the Russian-language (Tartu) 1988. — Providence, RI : American Mathematical Society, 1991. — Т. 86. — P. iv 123. — (Translations of Mathematical Monographs) — ISBN 0-8218-4546-2.
  9. Mikhail I. Kadets, Vladimir M. Kadets. Chapter 2.1 Steinitz's theorem on the sum range of a series, Chapter 7 The Steinitz theorem and B-convexity // Series in Banach spaces: Conditional and unconditional convergence. — Translated by Andrei Iacob from the Russian-language. — Basel : Birkhäuser Verlag, 1997. — Т. 94. — P. viii 156. — (Operator Theory: Advances and Applications) — ISBN 3-7643-5401-1.
  10. M. L. Balinski. On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — 1961. — Т. 11, вип. 2. — С. 431—434. — DOI:10.2140/pjm.1961.11.431.
  11. Suresh Venkatasubramanian. Planar graphs and Steinitz's theorem. — 2006.
  12. Ares Ribó Mor, Günter Rote, André Schulz. Small Grid Embeddings of 3-Polytopes // Discrete & Computational Geometry. — 2011. — Т. 45, вип. 1. — С. 65—87. — DOI:10.1007/s00454-010-9301-0.
  13. Kevin Buchin, André Schulz. Algorithms - 18th Annual European Symposium (ESA 2010). — Springer-Verlag, 2010. — Т. 6346. — P. 110—121. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-15775-2.
  14. André Schulz. Drawing 3-polytopes with good vertex resolution // Journal of Graph Algorithms and Applications. — 2011. — Т. 15, вип. 1. — С. 33—52. — DOI:10.7155/jgaa.00216. [Архівовано 2016-03-04 у Wayback Machine.]
  15. David Barnette, Branko Grünbaum. Preassigning the shape of a face // Pacific Journal of Mathematics. — 1970. — Т. 32, вип. 2. — С. 299—306. — DOI:10.2140/pjm.1970.32.299.
  16. David W. Barnette. Projections of 3-polytopes // Israel Journal of Mathematics. — 1970. — Т. 8, вип. 3. — С. 304—308. — DOI:10.1007/BF02771563.
  17. Günter M. Ziegler. Geometric Combinatorics. — American Mathematical Society, 2007. — Т. 13. — P. 628—642. — (IAS/Park City Mathematics Series) — ISBN 978-0-8218-3736-8.
  18. Oded Schramm. How to cage an egg // Inventiones Mathematicae. — 1992. — Т. 107, вип. 3. — С. 543—560. — DOI:10.1007/BF01231901.