Steinitz teorem

Steinitz sats  är en kombinatorisk beskrivning av oriktade grafer som bildas av kanterna och hörnen på en 3D konvex polyeder  - de är exakt ( enkla ) vertex 3-kopplade plana grafer (med minst fyra hörn) [1] [2] . Det vill säga, vilken konvex polytop som helst bildar en 3-kopplad plan graf, och vilken som helst 3-kopplad plan graf kan representeras som en konvex polytop. Av denna anledning kallas 3-kopplade plana grafer även polyedriska [3] .

Steinitz teorem är uppkallad efter Ernst Steinitz , som publicerade det första beviset för detta resultat 1916 [4] . Branko Grünbaum kallade detta teorem "det viktigaste och djupaste resultatet på 3-dimensionella polyedrar " [2] .

Namnet "Steinitzs teorem" är också tillämpligt på andra resultat av Steinitz:

Uttalande av satsen

En oriktad graf  är ett system av hörn och kanter , där varje kant förbinder två hörn. En graf kan bildas från vilken polyeder som helst om grafens hörn anses vara polyederns hörn och två hörn på grafen är förbundna med en kant om polyederns motsvarande hörn är ändpunkterna på dess kanter. Denna graf är känd som polyederns endimensionella skelett .

En graf är plan om dess hörn kan placeras på ett plan och kanterna på grafen kan ritas på detta plan som kurvor som förbinder dessa punkter, på ett sådant sätt att inga två kanter skär varandra, och hörnen ligger på sådana kurvor, om endast spetsen är ändpunkten för motsvarande kant. Med Faris teorem kan vi anta att kurvor i själva verket är segment . En graf är vertex-3-ansluten om, efter att ha tagit bort två av dess hörn, vilket par av de återstående hörnen kan kopplas samman med en bana.

Uttalandet av Steinitz sats i en riktning (lättare att bevisa) säger att grafen för vilken konvex polytop som helst är plan och 3-kopplad. Som visas i figuren kan planheten visas med hjälp av ett Schlegel-diagram  - om du placerar en punktljuskälla nära en av polyederns ytor och placerar ett plan på den andra sidan, bildas skuggorna av polyederns kanter en plan graf inbäddad i planet på ett sådant sätt att grafens kanter representeras som segment. 3-anslutningen för en polytopgraf är ett specialfall av Balinskys sats att grafen för vilken k - dimensionell konvex polytop som helst är k -ansluten [11] .

Påståendet på ett annat, mer komplicerat sätt säger att varje plan 3-kopplad graf är en graf av en konvex polyeder.

Vinster och relaterade resultat

Man kan bevisa ett mer rigoröst påstående av Steinitzs teorem, att vilken polyedrisk graf som helst kan realiseras som en konvex polyeder med hörn som har heltalskoordinater. Heltalen som erhålls i Steinitz ursprungliga bevis är en dubbel exponentiell funktion av antalet hörn av den givna polyedern. Att skriva dessa siffror kräver alltså ett exponentiellt antal bitar [12] . Efterföljande forskning fann dock en grafvisualiseringsalgoritm som endast kräver O( n ) bitar för varje vertex [13] [14] . Vi kan lätta på kravet att alla koordinater är heltal och tilldela koordinater på ett sådant sätt att x - koordinaterna för hörnen kommer att vara olika heltal i intervallet [0,2 n  − 4], och de andra två koordinaterna kommer att vara reella tal i intervallet [0,1], så att varje kant har minst en längd, medan polyederns volym kommer att begränsas till O( n ) [15] .

I vilken polytop som helst som representerar en given polyedrisk graf G är ytorna på G exakt cykler i G som inte delar upp G i två komponenter. Det vill säga att ta bort cykeln som motsvarar en yta från G ger en sammankopplad subgraf av G . Du kan specificera formen på valfri yta av polyedern i förväg - om du väljer en cykel C som inte delar upp grafen i delar och ordnar dess hörn i form av en tvådimensionell konvex polygon P , så finns det en polyedrisk representation G , där ytan som motsvarar C är kongruent med P [16] . Det är också alltid möjligt för en given polyedrisk graf G och en godtycklig cykel C att hitta en realisering där C bildar en realiseringssiluett under en parallell projektion [17] .

Köbe-Andreev- Thurstons cirkelpackningssats kan ses som ytterligare en förstärkning av Steinitz-satsen att vilken 3-kopplad plan graf som helst kan representeras som en konvex polyeder på ett sådant sätt att alla dess kanter vidrör samma enhetssfär [18] . Mer allmänt, om G  är en polyedrisk graf och K  är en slät tredimensionell konvex kropp , kan man hitta en polyedrisk representation av G där alla kanter berör K [19] .

Se även

Anteckningar

  1. Günter M. Ziegler. Kapitel 4. "Steinitz' sats för 3-polytoper" // Föreläsningar om polytoper. - 1995. - S. 103. - ISBN 0-387-94365-X .
  2. 12 Branko Grünbaum . Convex Polytopes / Volker Kaibel , Victor Klee , Günter M. Ziegler . — 2:a upplagan. - 2003. - S. 466. - ISBN 0-387-40409-0 , 978-0-387-40409-7.
  3. Weisstein, Eric W. Polyhedral graf  på Wolfram MathWorld- webbplatsen .
  4. Ernst Steinitz. Encyclopädie der mathematischen Wissenschaften . - 1922. - Nr IIIAB12 . - S. 1-139. Abgeschlossen den 31 augusti 1916
  5. Mariusz Zynel. Steinitz-satsen och dimensionen av ett vektorrum // Formaliserad matematik. - 1996. - V. 5 , nr. 8 . - s. 423-428.
  6. David Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap. Kvantitativa Steinitz satser med tillämpningar på flerfingrar grepp // Diskret och beräkningsgeometri. - 1992. - T. 7 , nummer. 1 . - s. 295-318. - doi : 10.1007/BF02187843 .
  7. Peter Rosenthal. Den anmärkningsvärda teorem av Lévy och Steinitz  // American Mathematical Monthly. - 1987. - T. 94 , nr. 4 . - s. 342-351. — .
  8. Wojciech Banaszczyk. Kapitel 3.10 Lévy-Steinitz-satsen // Additiv undergrupper av topologiska vektorrum. - Berlin: Springer-Verlag, 1991. - P. viii+178. - (Föreläsningsanteckningar i matematik). ISBN 3-540-53917-4 .
  9. VM Kadets, MI Kadets. Kapitel 6. Steinitz-satsen och B -konvexitet // Omarrangemang av serier i Banach-rum. — Översatt av Harold H. McFaden från det ryskspråkiga (Tartu) 1988. — Providence, RI: American Mathematical Society, 1991. — P. iv+123. — (Översättningar af matematiska monografier). — ISBN 0-8218-4546-2 .
  10. Mikhail I. Kadets, Vladimir M. Kadets. Kapitel 2.1 Steinitz sats om summaintervallet för en serie, Kapitel 7 Steinitz satsen och B -konvexitet // Serier i Banach-rum: Betingad och ovillkorlig konvergens. — Översatt av Andrei Iacob från det ryska språket. - Basel: Birkhäuser Verlag, 1997. - P. viii+156. - (Operatorteori: framsteg och tillämpningar). ISBN 3-7643-5401-1 .
  11. M. L. Balinsky. På grafstrukturen för konvexa polyedrar i n -rymden  // Pacific Journal of Mathematics . - 1961. - T. 11 , nr. 2 . - s. 431-434. - doi : 10.2140/pjm.1961.11.431 . Arkiverad 11 maj 2019.
  12. Suresh Venkatasubramanian. Plana grafer och Steinitz sats . - 2006. Arkiverad 29 december 2014.
  13. Ares Ribo Mor, Günter Rote, André Schulz. Små rutnätsinbäddningar av 3-polytoper // Diskret och beräkningsgeometri. - 2011. - T. 45 , nr. 1 . - S. 65-87. - doi : 10.1007/s00454-010-9301-0 .
  14. Kevin Buchin, Andre Schulz. Algoritmer - 18:e årliga europeiska symposiet (ESA 2010). - Springer-Verlag, 2010. - S. 110-121. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/978-3-642-15775-2 .
  15. André Schulz. Rita 3-polytoper med bra vertexupplösning  // Journal of Graph Algorithms and Applications. - 2011. - T. 15 , nr. 1 . - S. 33-52. - doi : 10.7155/jgaa.00216 . Arkiverad från originalet den 4 mars 2016.
  16. David Barnette, Branko Grünbaum. Förtilldelning av formen på ett ansikte  // Pacific Journal of Mathematics . - 1970. - T. 32 , nr. 2 . - s. 299-306. - doi : 10.2140/pjm.1970.32.299 . Arkiverad från originalet den 25 september 2015.
  17. David W. Barnette. Projektioner av 3-polytoper // Israel Journal of Mathematics. - 1970. - T. 8 , nr. 3 . - s. 304-308. - doi : 10.1007/BF02771563 .
  18. Günter M. Ziegler. Geometrisk kombinatorik / 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. Hur man burar ett ägg  // Inventiones Mathematicae . - 1992. - T. 107 , nr. 3 . - S. 543-560. - doi : 10.1007/BF01231901 .