Steinitz' sætning er en kombinatorisk beskrivelse af ikke- rettede grafer dannet af kanterne og hjørnerne af et 3D konveks polyeder - de er nøjagtigt ( simpel ) top 3-forbundne plane grafer (med mindst fire spidser) [1] [2] . Det vil sige, at enhver konveks polytop danner en 3-forbundet plan graf, og enhver 3-forbundet plan graf kan repræsenteres som en konveks polytop. Af denne grund kaldes 3-forbundne plane grafer også polyedriske [3] .
Steinitzs teorem er opkaldt efter Ernst Steinitz , som offentliggjorde det første bevis på dette resultat i 1916 [4] . Branko Grünbaum kaldte denne teorem "det vigtigste og dybeste resultat på 3-dimensionelle polyedre " [2] .
Navnet "Steinitz's teorem" er også anvendeligt til andre resultater af Steinitz:
En urettet graf er et system af toppunkter og kanter , hvor hver kant forbinder to toppunkter. En graf kan dannes ud fra et hvilket som helst polyeder, hvis grafens hjørner tages for at være polyederens spidser, og to spidser på grafen er forbundet med en kant, hvis polyederens tilsvarende spidser er endepunkterne på dets kanter. Denne graf er kendt som polyederens endimensionelle skelet .
En graf er plan , hvis dens toppunkter kan placeres på et plan, og kanterne af grafen kan tegnes på dette plan som kurver, der forbinder disse punkter, på en sådan måde, at ingen to kanter skærer hinanden, og toppunkterne ligger på sådanne kurver, hvis kun toppunktet er endepunktet for den tilsvarende kant. Ved Faris sætning kan vi antage, at kurver i virkeligheden er segmenter . En graf er vertex-3-forbundet , hvis, efter at have fjernet to af dens toppunkter, et hvilket som helst par af de resterende toppunkter kan forbindes med en sti.
Udtalelsen af Steinitz's sætning i én retning (lettere at bevise) siger, at grafen for enhver konveks polytop er plan og 3-forbundet. Som vist på figuren kan planaritet vises ved hjælp af et Schlegel-diagram - hvis du placerer en punktlyskilde nær en af polyederets flader, og placerer et plan på den anden side, dannes skyggerne af polyederens kanter en plan graf indlejret i planet på en sådan måde, at grafens kanter er repræsenteret som segmenter. 3-forbindelsen af en polytopgraf er et specialtilfælde af Balinskys sætning om, at grafen for enhver k - dimensionel konveks polytop er k - forbundet [11] .
Udsagnet på en anden, mere kompliceret måde siger, at enhver plan 3-forbundet graf er en graf af et konveks polyeder.
Man kan bevise en mere stringent påstand om Steinitz's sætning, at enhver polyhedral graf kan realiseres som et konveks polyeder med toppunkter med heltalskoordinater. Heltallene opnået i Steinitz' originale bevis er en dobbelt eksponentiel funktion af antallet af hjørner af det givne polyeder. At skrive disse tal kræver således et eksponentielt antal bits [12] . Efterfølgende forskning fandt dog en grafvisualiseringsalgoritme , der kun kræver O( n ) bits for hvert toppunkt [13] [14] . Vi kan slække på kravet om, at alle koordinater skal være heltal og tildele koordinater på en sådan måde, at x - koordinaterne for hjørnerne vil være forskellige heltal i intervallet [0,2 n − 4], og de to andre koordinater vil være reelle tal i intervallet [0,1], således at hver kant har mindst én længde, mens polyederens volumen vil være begrænset til O( n ) [15] .
I enhver polytop, der repræsenterer en given polyhedral graf G , er flader af G nøjagtigt cyklusser i G , der ikke deler G i to komponenter. Det vil sige, at fjernelse af cyklussen svarende til et ansigt fra G giver en forbundet undergraf af G. Du kan specificere formen på en hvilken som helst side af polyederet på forhånd - hvis du vælger en cyklus C , der ikke opdeler grafen i dele, og arrangerer dens hjørner i form af en todimensional konveks polygon P , så er der en polyhedral repræsentation G , hvor fladen svarende til C er kongruent med P [16] . Det er også altid muligt for en given polyedrisk graf G og en vilkårlig cyklus C at finde en realisering, hvor C danner en realiseringssilhuet under en parallel projektion [17] .
Köbe-Andreev- Thurstons cirkelpakningssætning kan ses som endnu en styrkelse af Steinitz-sætningen om, at enhver 3-forbundet plan graf kan repræsenteres som et konveks polyeder på en sådan måde, at alle dets kanter rører den samme enhedskugle [18] . Mere generelt, hvis G er en polyedrisk graf, og K er en glat tredimensional konveks krop , kan man finde en polyhedral repræsentation af G , hvor alle kanter rører K [19] .