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:
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.
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] .