Теорема Штайніца
Теорема Штайніца — це комбінаторний опис неорієнтованих графів, утворених ребрами й вершинами тривимірного опуклого многогранника — вони точно є (простими) вершинно 3-зв'язними планарними графами (щонайменше з чотирма вершинами)[1][2]. Тобто будь-який опуклий многогранник утворює 3-зв'язний планарний граф, і будь-який 3-зв'язний планарний граф можна подати як опуклий многогранник. З цієї причини 3-зв'язні планарні графи називають також поліедральними.
Теорему названо ім'ям Ернста Штайніца, який опублікував перше доведення цього результату 1916 року[3]. Бранко Ґрюнбаум назвав цю теорему «найважливішим і найглибшим результатом про тривимірні політопи»[2].
Назву «теорема Штайніца» також застосовують до інших результатів Штайніца:
- лема Штайніца про заміщення — про те, що будь-який базис векторного простору має однакове число векторів[4];
- теорема, що якщо опукла оболонка множини точок містить одиничну сферу, існує скінченна підмножина точок, опукла оболонка якої містить концентричну сферу меншого розміру[5];
- векторне узагальнення Штайніца теореми Рімана про перегрупування умовно збіжних рядів[6][7][8][9].
Неорієнтований граф — це система вершин і ребер, кожне ребро поєднує дві вершини. З будь-якого многогранника можна утворити граф, якщо за вершини графа прийняти вершини многогранника і з'єднати ребром дві вершини графа, якщо відповідні вершини многогранника є кінцевими точками його ребер. Цей граф відомий як одновимірний кістяк многогранника.
Граф є планарним, якщо його вершини можна позначити точками на площині і намалювати на цій площині ребра графа як криві, що з'єднують ці точки, так, щоб жодні два ребра не перетиналися, а точка лежала на кривій, тільки якщо вершина є кінцевою точкою відповідного ребра. За теоремою Фарі можна вважати, що криві, насправді, є відрізками. Граф вершинно 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].
- Вкладення Татта — метод отримання діаграми Шлегеля поліедрального подання графа за допомогою розв'язання системи лінійних рівнянь.
- ↑ Günter M. Ziegler. Chapter 4. «Steinitz' Theorem for 3-Polytopes» // Lectures on Polytopes. — 1995. — P. 103. — ISBN 0-387-94365-X.
- ↑ а б 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.
- ↑ Ernst Steinitz. Encyclopädie der mathematischen Wissenschaften. — 1922. — № IIIAB12. Abgeschlossen am 31. August 1916
- ↑ 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.
- ↑ 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: .
- ↑ Peter Rosenthal. The remarkable theorem of Lévy and Steinitz // American Mathematical Monthly. — 1987. — Т. 94, вип. 4. — С. 342—351.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ M. L. Balinski. On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — 1961. — Т. 11, вип. 2. — С. 431—434. — DOI: .
- ↑ Suresh Venkatasubramanian. Planar graphs and Steinitz's theorem. — 2006.
- ↑ Ares Ribó Mor, Günter Rote, André Schulz. Small Grid Embeddings of 3-Polytopes // Discrete & Computational Geometry. — 2011. — Т. 45, вип. 1. — С. 65—87. — DOI: .
- ↑ Kevin Buchin, André Schulz. Algorithms - 18th Annual European Symposium (ESA 2010). — Springer-Verlag, 2010. — Т. 6346. — P. 110—121. — (Lecture Notes in Computer Science) — DOI:
- ↑ André Schulz. Drawing 3-polytopes with good vertex resolution // Journal of Graph Algorithms and Applications. — 2011. — Т. 15, вип. 1. — С. 33—52. — DOI: . [Архівовано 2016-03-04 у Wayback Machine.]
- ↑ David Barnette, Branko Grünbaum. Preassigning the shape of a face // Pacific Journal of Mathematics. — 1970. — Т. 32, вип. 2. — С. 299—306. — DOI: .
- ↑ David W. Barnette. Projections of 3-polytopes // Israel Journal of Mathematics. — 1970. — Т. 8, вип. 3. — С. 304—308. — DOI: .
- ↑ 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.
- ↑ Oded Schramm. How to cage an egg // Inventiones Mathematicae. — 1992. — Т. 107, вип. 3. — С. 543—560. — DOI: .
В іншому мовному розділі є повніша стаття Steinitz's theorem(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської.
|