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

Перейти к навигацииПерейти к поиску

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

Теорема Штайница названа именем Эрнста Штайница, который опубликовал первое доказательство этого результата в 1916 году[4]. Бранко Грюнбаум назвал эту теорему «наиболее важным и глубочайшим результатом о 3-мерных многогранниках»[2].

Название «Теорема Штайница» также применимо к другим результатам Штайница:

Утверждение теоремы

Освещение скелета выпуклого многогранника из точечного источника света, близкого к одной из его граней, даёт тень в виде плоской диаграммы Шлегеля.

Неориентированный граф — это система вершин и рёбер, каждое ребро соединяет две вершины. Из любого многогранника можно образовать граф, если вершинами графа принять вершины многогранника и соединять ребром две вершины графа, если соответствующие вершины многогранника являются конечными точками его рёбер. Этот граф известен как одномерный остов многогранника.

Граф является планарным, если его вершины можно расположить на плоскости и нарисовать на этой плоскости рёбра графа как кривые, соединяющие эти точки, таким образом, что никакие два ребра не пересекаются, а вершины лежат на таких кривых, если только вершина является конечной точкой соответствующего ребра. По теореме Фари можно считать, что кривые, на самом деле, являются отрезками. Граф вершинно 3-связен, если после удаления любых двух его вершин любую пару из оставшихся вершин можно соединить путём.

Утверждение теоремы Штайница в одном направлении (более простом для доказательства) гласит, что граф любого выпуклого многогранника является планарным и 3-связным. Как показано на рисунке, планарность можно показать с помощью диаграммы Шлегеля — если разместить точечный источник света вблизи одной из граней многогранника, а с другой стороны разместить плоскость, тени рёбер многогранника образуют планарный граф, вложенный в плоскость таким образом, что рёбра графа представлены в виде отрезков. 3-связность графа многогранника является частным случаем теоремы Балинского, что граф любого k-мерного выпуклого многогранника является k-связным[11].

Утверждение в другую, более сложную, сторону гласит, что любой планарный 3-связный граф является графом выпуклого многогранника.

Усиления и связанные результаты

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

В любом многограннике, который представляет заданный полиэдральный граф G, грани G являются в точности циклами в G, которые не делят G на две компоненты. То есть, удаление цикла, соответствующего грани, из G даёт связный подграф G. Можно заранее указать форму любой одной грани многогранника — если выбрать цикл C, не разделяющий граф на части, и его вершины расположить в виде двумерного выпуклого многоугольника P, то существует полиэдральное представление G, в котором грань, соответствующая C, конгруэнтна P[16]. Также всегда есть возможность для заданного полиэдрального графа G и произвольного цикла C найти реализацию, при которой C образует силуэт реализации при параллельной проекции[17].

Теорему об упаковке кругов Кёбе — Андреева — Тёрстона можно рассматривать как другое усиление теоремы Штайница, что любой 3-связный планарный граф может быть представлен в виде выпуклого многогранника таким образом, что все его рёбра касаются одной и той же единичной сферы[англ.]*[18]. Более обще, если G — полиэдральный граф и K — гладкое трёхмерное выпуклое тело, можно найти полиэдральное представление G, в котором все рёбра касаются K[19].

См. также

Примечания

  1. ↑ Günter M. Ziegler. Chapter 4. «Steinitz' Theorem for 3-Polytopes» // Lectures on Polytopes. — 1995. — P. 103. — ISBN 0-387-94365-X.
  2. ↑ 1 2 Branko Grünbaum. Convex Polytopes / Volker Kaibel, Victor Klee, Günter M. Ziegler. — 2nd edition. — 2003. — P. 466. — ISBN 0-387-40409-0, 978-0-387-40409-7.
  3. ↑ Weisstein, Eric W. Polyhedral graph (англ.) на сайте Wolfram MathWorld.
  4. ↑ Ernst Steinitz. Encyclopädie der mathematischen Wissenschaften. — 1922. — № IIIAB12. — S. 1—139. Abgeschlossen am 31. August 1916
  5. ↑ Mariusz Zynel. The Steinitz theorem and the dimension of a vector space // Formalized Mathematics. — 1996. — Т. 5, вып. 8. — P. 423—428.
  6. ↑ David Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap. Quantitative Steinitz's theorems with applications to multifingered grasping // Discrete & Computational Geometry. — 1992. — Т. 7, вып. 1. — P. 295–318. — doi:10.1007/BF02187843.
  7. ↑ Peter Rosenthal. The remarkable theorem of Lévy and Steinitz // American Mathematical Monthly. — 1987. — Т. 94, вып. 4. — P. 342—351. — JSTOR 2323094.
  8. ↑ Wojciech Banaszczyk. Chapter 3.10 The Lévy-Steinitz theorem // Additive subgroups of topological vector spaces. — Berlin: Springer-Verlag, 1991. — P. viii+178. — (Lecture Notes inMathematics). — ISBN 3-540-53917-4.
  9. ↑ 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. — P. iv+123. — (Translations of Mathematical Monographs). — ISBN 0-8218-4546-2.
  10. ↑ 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. — P. viii+156. — (Operator Theory: Advances and Applications). — ISBN 3-7643-5401-1.
  11. ↑ M. L. Balinski. On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — 1961. — Т. 11, вып. 2. — P. 431—434. — doi:10.2140/pjm.1961.11.431. Архивировано 11 мая 2019 года.
  12. ↑ Suresh Venkatasubramanian. Planar graphs and Steinitz's theorem. — 2006. Архивировано 29 декабря 2014 года.
  13. ↑ Ares Ribó Mor, Günter Rote, André Schulz. Small Grid Embeddings of 3-Polytopes // Discrete & Computational Geometry. — 2011. — Т. 45, вып. 1. — P. 65—87. — doi:10.1007/s00454-010-9301-0.
  14. ↑ Kevin Buchin, André Schulz. Algorithms - 18th Annual European Symposium (ESA 2010). — Springer-Verlag, 2010. — P. 110—121. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-15775-2.
  15. ↑ André Schulz. Drawing 3-polytopes with good vertex resolution // Journal of Graph Algorithms and Applications. — 2011. — Т. 15, вып. 1. — P. 33—52. — doi:10.7155/jgaa.00216. Архивировано 4 марта 2016 года.
  16. ↑ David Barnette, Branko Grünbaum. Preassigning the shape of a face // Pacific Journal of Mathematics. — 1970. — Т. 32, вып. 2. — P. 299—306. — doi:10.2140/pjm.1970.32.299. Архивировано 25 сентября 2015 года.
  17. ↑ David W. Barnette. Projections of 3-polytopes // Israel Journal of Mathematics. — 1970. — Т. 8, вып. 3. — P. 304—308. — doi:10.1007/BF02771563.
  18. ↑ Günter M. Ziegler. Geometric Combinatorics / Ezra Miller, Victor Reiner, Bernd Sturmfels. — American Mathematical Society, 2007. — P. 628—642. — (IAS/Park City Mathematics Series). — ISBN 978-0-8218-3736-8.
  19. ↑ Oded Schramm. How to cage an egg // Inventiones Mathematicae. — 1992. — Т. 107, вып. 3. — P. 543—560. — doi:10.1007/BF01231901.