Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Теорема Штайніца це комбінаторний опис неорієнтованих графів утворених ребрами й вершинами тривимірного опуклого многогр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки

  1. Günter M. Ziegler. Chapter 4. «Steinitz' Theorem for 3-Polytopes» // Lectures on Polytopes. — 1995. — P. 103. — .
  2. Branko Grünbaum. Convex Polytopes / Volker Kaibel, [en], [en]. — 2nd edition. — 2003. — P. 466. — , 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) — .
  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) — .
  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) — .
  10. M. L. Balinski. On the graph structure of convex polyhedra in n-space // . — 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.
  15. David Barnette, Branko Grünbaum. Preassigning the shape of a face // . — 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) — .
  18. Oded Schramm. How to cage an egg // Inventiones Mathematicae. — 1992. — Т. 107, вип. 3. — С. 543—560. — DOI:10.1007/BF01231901.
В іншому мовному розділі є повніша стаття Steinitz's theorem(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської.
  • Дивитись автоперекладену версію статті з мови «англійська».
  • Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії!
  • Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії.
  • Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті.
  • Докладні рекомендації: див. .

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Teorema Shtajnica ce kombinatornij opis neoriyentovanih grafiv utvorenih rebrami j vershinami trivimirnogo opuklogo mnogogrannika voni tochno ye prostimi vershinno 3 zv yaznimi planarnimi grafami shonajmenshe z chotirma vershinami Tobto bud yakij opuklij mnogogrannik utvoryuye 3 zv yaznij planarnij graf i bud yakij 3 zv yaznij planarnij graf mozhna podati yak opuklij mnogogrannik Z ciyeyi prichini 3 zv yazni planarni grafi nazivayut takozh poliedralnimi Teoremu nazvano im yam yakij opublikuvav pershe dovedennya cogo rezultatu 1916 roku Branko Gryunbaum nazvav cyu teoremu najvazhlivishim i najglibshim rezultatom pro trivimirni politopi Nazvu teorema Shtajnica takozh zastosovuyut do inshih rezultativ Shtajnica lema Shtajnica pro zamishennya pro te sho bud yakij bazis vektornogo prostoru maye odnakove chislo vektoriv teorema sho yaksho opukla obolonka mnozhini tochok mistit odinichnu sferu isnuye skinchenna pidmnozhina tochok opukla obolonka yakoyi mistit koncentrichnu sferu menshogo rozmiru vektorne uzagalnennya Shtajnica teoremi Rimana pro peregrupuvannya umovno zbizhnih ryadiv Tverdzhennya teoremiVisvitlennya skeleta opuklogo bagatogrannika tochkovim dzherelom svitla blizkim do odniyeyi z jogo granej daye tin u viglyadi ploskoyi diagrami Shlegelya Neoriyentovanij graf ce sistema vershin i reber kozhne rebro poyednuye dvi vershini Z bud yakogo mnogogrannika mozhna utvoriti graf yaksho za vershini grafa prijnyati vershini mnogogrannika i z yednati rebrom dvi vershini grafa yaksho vidpovidni vershini mnogogrannika ye kincevimi tochkami jogo reber Cej graf vidomij yak odnovimirnij kistyak mnogogrannika Graf ye planarnim yaksho jogo vershini mozhna poznachiti tochkami na ploshini i namalyuvati na cij ploshini rebra grafa yak krivi sho z yednuyut ci tochki tak shob zhodni dva rebra ne peretinalisya a tochka lezhala na krivij tilki yaksho vershina ye kincevoyu tochkoyu vidpovidnogo rebra Za teoremoyu Fari mozhna vvazhati sho krivi naspravdi ye vidrizkami Graf vershinno 3 zv yaznij yaksho pislya vidalennya bud yakih dvoh jogo vershin bud yaku paru z reshti vershin mozhna z yednati shlyahom Teorema Shtajnica v odnomu napryamku prostishomu dlya dovedennya stverdzhuye sho graf bud yakogo opuklogo mnogogrannika ye planarnim i 3 zv yaznim Yak pokazano na malyunku planarnist mozhna pokazati za dopomogoyu diagrami Shlegelya yaksho rozmistiti tochkove dzherelo svitla poblizu odniyeyi z granej bagatogrannika a z inshogo boku rozmistiti ploshinu tini reber mnogogrannika utvoryuyut planarnij graf ukladenij u ploshinu takim chinom sho rebra grafa predstavleni vidrizkami 3 zv yaznist grafa mnogogrannika ye okremim vipadkom sho graf bud yakogo k vimirnogo opuklogo mnogogrannika ye k zv yaznim Tverdzhennya v inshij skladnishij bik bud yakij planarnij 3 zv yaznij graf ye grafom opuklogo mnogogrannika Posilennya ta pov yazani rezultatiMozhna dovesti strogishe tverdzhennya teoremi Shtajnica sho bud yakij poliedralnij graf mozhna realizuvati yak opuklij mngogogrannik iz vershinami sho mayut cili koordinati Cili chisla sho vihodyat v originalnomu dovedenni ye en vid chisla vershin zadanogo mnogogrannika Takim chinom zapis cih chisel vimagaye eksponencialnogo chisla bitiv Odnak u podalshih doslidzhennyah znajdeno algoritm vizualizaciyi grafiv yakij vimagaye lishe O n bitiv dlya kozhnoyi vershini Mozhna poslabiti vimogu shob usi koordinati buli cilimi ta priznachiti koordinati tak sho x koordinati vershin budut riznimi cilimi chislami v intervali 0 2n 4 a inshi dvi koordinati budut dijsnimi chislami z intervalu 0 1 todi kozhne rebro matime dovzhinu ne menshu vid odinici todi yak ob yem mnogogrannika bude obmezhenij O n U bud yakomu mnogogranniku yakij vidpovidaye danomu poliedralnomu grafu G displaystyle G grani ye tochno ciklami v G displaystyle G yaki ne dilyat G displaystyle G na dvi komponenti Tobto vidalennya z G displaystyle G ciklu vidpovidnogo grani daye zv yaznij pidgraf G displaystyle G taki cikli nazivayut periferijnimi Mozhna zazdalegid vkazati formu bud yakoyi odniyeyi grani bagatogrannika yaksho vibrati cikl C displaystyle C yakij ne rozdilyaye grafa na chastini i jogo vershini roztashuvati u viglyadi dvovimirnogo opuklogo mnogokutnika P displaystyle P isnuye poliedralne podannya G displaystyle G v yakomu gran vidpovidna C displaystyle C kongruentna P displaystyle P Takozh zavzhdi ye mozhlivist dlya zadanogo poliedralnogo grafa G displaystyle G i dovilnogo ciklu C displaystyle C znajti realizaciyu za yakoyi C displaystyle C utvoryuye siluet realizaciyi pri paralelnij proyekciyi Kebe Andryeyeva Terstona mozhna rozglyadati yak inshe posilennya teoremi Shtajnica sho bud yakij 3 zv yaznij planarnij graf mozhna podati u viglyadi opuklogo mnogogrannika tak sho vsi jogo rebra dotikatimutsya do odniyeyi j tiyeyi samoyi odinichnoyi sferi Zagalnishe yaksho G displaystyle G poliedralnij graf i K displaystyle K gladke trivimirne opukle tilo mozhna znajti poliedralne podannya G displaystyle G v yakomu vsi rebra dotikayutsya do K displaystyle K Div takozhVkladennya Tatta metod otrimannya diagrami Shlegelya poliedralnogo podannya grafa za dopomogoyu rozv yazannya sistemi linijnih rivnyan PrimitkiGunter M Ziegler Chapter 4 Steinitz Theorem for 3 Polytopes Lectures on Polytopes 1995 P 103 ISBN 0 387 94365 X Branko Grunbaum Convex Polytopes Volker Kaibel en en 2nd edition 2003 P 466 ISBN 0 387 40409 0 978 0 387 40409 7 Ernst Steinitz Encyclopadie 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 T 5 vip 8 S 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 amp Computational Geometry 1992 T 7 vip 1 S 295 318 DOI 10 1007 BF02187843 Peter Rosenthal The remarkable theorem of Levy and Steinitz American Mathematical Monthly 1987 T 94 vip 4 S 342 351 Wojciech Banaszczyk Chapter 3 10 The Levy Steinitz theorem Additive subgroups of topological vector spaces Berlin Springer Verlag 1991 T 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 T 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 Birkhauser Verlag 1997 T 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 1961 T 11 vip 2 S 431 434 DOI 10 2140 pjm 1961 11 431 Suresh Venkatasubramanian Planar graphs and Steinitz s theorem 2006 Ares Ribo Mor Gunter Rote Andre Schulz Small Grid Embeddings of 3 Polytopes Discrete amp Computational Geometry 2011 T 45 vip 1 S 65 87 DOI 10 1007 s00454 010 9301 0 Kevin Buchin Andre Schulz Algorithms 18th Annual European Symposium ESA 2010 Springer Verlag 2010 T 6346 P 110 121 Lecture Notes in Computer Science DOI 10 1007 978 3 642 15775 2 Andre Schulz Drawing 3 polytopes with good vertex resolution Journal of Graph Algorithms and Applications 2011 T 15 vip 1 S 33 52 DOI 10 7155 jgaa 00216 David Barnette Branko Grunbaum Preassigning the shape of a face 1970 T 32 vip 2 S 299 306 DOI 10 2140 pjm 1970 32 299 David W Barnette Projections of 3 polytopes Israel Journal of Mathematics 1970 T 8 vip 3 S 304 308 DOI 10 1007 BF02771563 Gunter M Ziegler Geometric Combinatorics American Mathematical Society 2007 T 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 T 107 vip 3 S 543 560 DOI 10 1007 BF01231901 V inshomu movnomu rozdili ye povnisha stattya Steinitz s theorem angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad

Дата публікації:
Топ