Перегляд вихідного коду сторінки Теорема Штайніца

'''Теорема Штайніца'''&nbsp;— це [[Комбінаторика багатогранників|комбінаторний опис]] [[Орієнтований граф|неорієнтованих графів]], утворених ребрами й вершинами тривимірного [[Опуклий многогранник|опуклого многогранника]]&nbsp;— вони точно є ([[Словник термінів теорії графів#П|простими]]) [[K-вершинно-зв'язний граф|вершинно 3-зв'язними]] [[Планарний граф|планарними графами]] (щонайменше з чотирма вершинами)<ref>{{Книга
|заголовок = Lectures on Polytopes
|автор = Günter M. Ziegler
|рік = 1995
|ISBN = 0-387-94365-X
|частина = Chapter 4. «Steinitz' Theorem for 3-Polytopes»
|pages = 103
}}</ref><ref name="grun">{{Книга
|автор = [[Бранко Ґрюнбаум|Branko Grünbaum]]
|видання = 2nd edition
|відповідальний = Volker Kaibel, {{нп|Віктор Клі|Victor Klee||Victor Klee}}, {{нп|Ґюнтер Ціґлер|Günter M. Ziegler||Günter M. Ziegler}}
|рік = 2003
|ISBN = 0-387-40409-0, 978-0-387-40409-7
|pages = 466
|назва = Convex Polytopes
}}</ref>. Тобто будь-який опуклий многогранник утворює 3-зв'язний планарний граф, і будь-який 3-зв'язний планарний граф можна подати як опуклий многогранник. З цієї причини 3-зв'язні планарні графи називають також [[Багатогранний граф|поліедральними]].

Теорему названо ім'ям [[Ернст Штайніц|Ернста Штайніца]], який опублікував перше доведення цього результату 1916 року<ref>{{Стаття|author=Ernst Steinitz|title=Encyclopädie der mathematischen Wissenschaften|рік=1922|номер=IIIAB12|url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN360609767&DMDID=dmdlog203}} Abgeschlossen am 31. August 1916</ref>. [[Бранко Ґрюнбаум]] назвав цю теорему «найважливішим і найглибшим результатом про [[Многогранник|тривимірні політопи]]»<ref name="grun"/>.

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

* [[лема Штайніца про заміщення]]&nbsp;— про те, що будь-який базис [[Векторний простір|векторного простору]] має однакове число векторів<ref>{{Стаття|title=The Steinitz theorem and the dimension of a vector space|author=Mariusz Zynel|видання=Formalized Mathematics|том=5|issue=8|рік=1996|pages=423—428|id={{citeseerx|10.1.1.79.1707}}}}</ref>;
* теорема, що якщо [[опукла оболонка]] множини точок містить одиничну сферу, існує скінченна [[підмножина]] точок, опукла оболонка якої містить концентричну сферу меншого розміру<ref>{{Стаття|title=Quantitative Steinitz's theorems with applications to multifingered grasping|author=David Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap|видання=Discrete & Computational Geometry|том=7|issue=1|рік=1992|doi=10.1007/BF02187843|pages=295–318}}</ref>;
* векторне узагальнення Штайніца [[Теорема Рімана про умовно збіжний ряд|теореми Рімана]] про перегрупування [[Умовна збіжність|умовно збіжних рядів]]<ref>{{Стаття|title=The remarkable theorem of Lévy and Steinitz|url=https://archive.org/details/sim_american-mathematical-monthly_1987-04_94_4/page/342|author=Peter Rosenthal|видання=American Mathematical Monthly|том=94|issue=4|рік=1987|pages=342—351}}</ref><ref>
{{Книга
|автор = Wojciech Banaszczyk
|частина = Chapter 3.10 The Lévy-Steinitz theorem
|заголовок = Additive subgroups of topological vector spaces
|серія = Lecture Notes inMathematics
|том = 1466
|видавництво = Springer-Verlag
|місце = Berlin
|рік = 1991
|pages = viii+178
|ISBN = 3-540-53917-4
}}</ref><ref>{{Книга
|автор = 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
|серія = Translations of Mathematical Monographs
|том = 86
|видавництво = American Mathematical Society
|місце = Providence, RI
|рік = 1991
|pages = iv+123
|ISBN = 0-8218-4546-2
}}</ref><ref>
{{Книга
|автор = 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
|серія = Operator Theory: Advances and Applications
|том = 94
|видавництво = Birkhäuser Verlag
|місце = Basel
|рік = 1997
|pages = viii+156
|ISBN = 3-7643-5401-1
}}</ref>.

== Твердження теореми ==
[[Файл:Schegel_diagram_as_shadow.png|міні| Висвітлення скелета опуклого багатогранника точковим джерелом світла, близьким до однієї з його граней, дає тінь у вигляді плоскої [[Діаграма Шлегеля|діаграми Шлегеля]].]]
[[Орієнтований граф|Неорієнтований граф]]&nbsp;— це система [[Вершина (теорія графів)|вершин]] і [[Граф (математика)|ребер]], кожне ребро поєднує дві вершини. З будь-якого многогранника можна утворити граф, якщо за вершини графа прийняти [[Вершина (геометрія)|вершини]] многогранника і з'єднати ребром дві вершини графа, якщо відповідні вершини многогранника є кінцевими точками його ребер. Цей граф відомий як [[Симпліціальний комплекс#Пов'язані визначення|одновимірний кістяк]] многогранника.

Граф є [[Планарний граф|планарним]], якщо його вершини можна позначити точками на [[Двовимірний простір|площині]] і намалювати на цій площині ребра графа як криві, що з'єднують ці точки, так, щоб жодні два ребра не перетиналися, а точка лежала на кривій, тільки якщо вершина є кінцевою точкою відповідного ребра. За [[Теорема Фарі про розпрямлення графа|теоремою Фарі]] можна вважати, що криві, насправді, є [[Відрізок|відрізками]]. Граф [[K-вершинно-зв'язний граф|вершинно 3-зв'язний]], якщо після видалення будь-яких двох його вершин будь-яку пару з решти вершин можна з'єднати [[Шлях (теорія графів)|шляхом]].

Теорема Штайніца в одному напрямку (простішому для доведення) стверджує, що граф будь-якого опуклого многогранника є планарним і 3-зв'язним. Як показано на малюнку, планарність можна показати за допомогою [[Діаграма Шлегеля|діаграми Шлегеля]]&nbsp;— якщо розмістити [[точкове джерело]] світла поблизу однієї з граней багатогранника, а з іншого боку розмістити площину, тіні ребер многогранника утворюють планарний граф, укладений у площину таким чином, що ребра графа представлені відрізками. 3-зв'язність графа многогранника є окремим випадком [[Теорема Балінського|теореми Балінського]], що граф будь-якого ''k''-вимірного [[Опуклий політоп|опуклого многогранника]] є ''k''-зв'язним<ref>{{Стаття|author=M. L. Balinski|title=On the graph structure of convex polyhedra in ''n''-space|видання=[[Pacific Journal of Mathematics]]|том=11|issue=2|рік=1961|pages=431—434|url=http://projecteuclid.org/euclid.pjm/1103037323|doi=10.2140/pjm.1961.11.431}}</ref>.

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

== Посилення та пов'язані результати ==
Можна довести строгіше твердження теореми Штайніца, що будь-який поліедральний граф можна реалізувати як опуклий мнгогогранник із вершинами, що мають цілі координати. Цілі числа, що виходять в оригінальному доведенні, є {{Не перекладено|Двічі експоненціальна функція|двічі експоненціальною функцією|en|double exponential function}} від числа вершин заданого многогранника. Таким чином, запис цих чисел вимагає експоненціального числа бітів<ref>{{Стаття|title=Planar graphs and Steinitz's theorem|author=Suresh Venkatasubramanian|рік=2006|url=http://geomblog.blogspot.com/2006/08/planar-graphs-and-steinitzs-theorem.html}}</ref>. Однак у подальших дослідженнях знайдено алгоритм [[Візуалізація графів|візуалізації графів]], який вимагає лише O(''n'') бітів для кожної вершини<ref>{{Стаття|author=Ares Ribó Mor, Günter Rote, André Schulz|title=Small Grid Embeddings of 3-Polytopes|видання=Discrete & Computational Geometry|том=45|issue=1|pages=65—87|doi=10.1007/s00454-010-9301-0|рік=2011}}</ref><ref>{{Книга
|автор = Kevin Buchin, André Schulz
|рік = 2010
|заголовок = Algorithms - 18th Annual European Symposium (ESA 2010)
|серія = Lecture Notes in Computer Science
|видавництво = Springer-Verlag
|том = 6346
|pages = 110—121
|doi = 10.1007/978-3-642-15775-2
}}</ref>. Можна послабити вимогу, щоб усі координати були цілими та призначити координати так, що ''x''-координати вершин будуть різними цілими числами в інтервалі [0,2''n'' − 4], а інші дві координати будуть [[Дійсне число|дійсними числами]] з інтервалу [0,1], тоді кожне ребро матиме довжину не меншу від одиниці, тоді як об'єм многогранника буде обмежений O(''n'')<ref>{{Стаття|author=André Schulz|title=Drawing 3-polytopes with good vertex resolution|видання=Journal of Graph Algorithms and Applications|рік=2011|том=15|issue=1|pages=33—52|url=http://jgaa.info/accepted/2011/Schulz2011.15.1.pdf|doi=10.7155/jgaa.00216}} {{Webarchive|url=https://web.archive.org/web/20160304050113/http://jgaa.info/accepted/2011/Schulz2011.15.1.pdf |date=2016-03-04 }}</ref>.

У будь-якому многограннику, який відповідає даному поліедральному графу <math>G</math>, грані є точно [[Цикл (теорія графів)|циклами]] в ''<math>G</math>'', які не ділять ''<math>G</math>'' на дві компоненти. Тобто, видалення з <math>G</math> циклу, відповідного грані, дає [[Зв'язний граф|зв'язний]] підграф ''<math>G</math>'' (такі цикли називають [[Периферійний цикл|периферійними]]). Можна заздалегідь вказати форму будь-якої однієї грані багатогранника&nbsp;— якщо вибрати цикл ''<math>C</math>'', який не розділяє графа на частини, і його вершини розташувати у вигляді двовимірного [[Опуклий многокутник|опуклого многокутника]] ''<math>P</math>'', існує поліедральне подання ''<math>G</math>'', в якому грань, відповідна ''<math>C</math>'', конгруентна ''<math>P</math>''<ref>{{Стаття|title=Preassigning the shape of a face|author=David Barnette, Branko Grünbaum|видання=[[Pacific Journal of Mathematics]]|том=32|issue=2|рік=1970|pages=299—306|url=http://projecteuclid.org/euclid.pjm/1102977361|doi=10.2140/pjm.1970.32.299}}</ref>. Також завжди є можливість для заданого поліедрального графа ''<math>G</math>'' і довільного циклу ''<math>C</math>'' знайти реалізацію, за якої ''<math>C</math>'' утворює [[Силует (графіка)|силует]] реалізації при [[Проєкція (математика)|паралельній проєкції]]<ref>{{Стаття|author=David W. Barnette|title=Projections of 3-polytopes|видання=Israel Journal of Mathematics|том=8|issue=3|рік=1970|pages=304—308|doi=10.1007/BF02771563}}</ref>.

[[Теорема про пакування кіл|Теорему про пакування кіл]] Кебе&nbsp;— Андрєєва&nbsp;— [[Вільям Терстон|Терстона]] можна розглядати як інше посилення теореми Штайніца, що будь-який 3-зв'язний планарний граф можна подати у вигляді опуклого многогранника так, що всі його ребра дотикатимуться до однієї й тієї самої [[Одинична сфера|одиничної сфери]]<ref>{{Книга
|pages = 628—642
|автор = Günter M. Ziegler
|заголовок = Geometric Combinatorics
|том = 13
|серія = IAS/Park City Mathematics Series
|видавництво = [[Американське математичне товариство|American Mathematical Society]]
|рік = 2007
|ISBN = 978-0-8218-3736-8
}}</ref>. Загальніше, якщо ''<math>G</math>''&nbsp;— поліедральний граф і ''<math>K</math>''&nbsp;— гладке тривимірне [[Опукла множина|опукле тіло]], можна знайти поліедральне подання ''<math>G</math>'', в якому всі ребра дотикаються до ''<math>K</math>''<ref>{{Стаття|author=Oded Schramm|title=How to cage an egg|url=https://archive.org/details/sim_inventiones-mathematicae_1992-03_107_3/page/543|видання=[[Inventiones Mathematicae]]|том=107|рік=1992|issue=3|pages=543—560|doi=10.1007/BF01231901}}</ref>.

== Див. також ==
* [[Вкладення Татта]]&nbsp;— метод отримання [[Діаграма Шлегеля|діаграми Шлегеля]] поліедрального подання графа за допомогою розв'язання [[Система лінійних алгебраїчних рівнянь|системи лінійних рівнянь]].

== Примітки ==
{{Reflist|2}}

{{Бібліоінформація}}
{{Перекласти|en|Steinitz's theorem}}

[[Категорія:Теореми дискретної геометрії]]
[[Категорія:Теореми теорії графів]]
[[Категорія:Комбінаторика многогранників]]
[[Категорія:Геометрична теорія графів]]
[[Категорія:Планарні графи]]
[[Категорія:1916 у науці]]