Steinitzin teoreema on kombinatorinen kuvaus suuntaamattomista graafista , jotka muodostuvat 3D- konveksin monitahoisen reunoista ja pisteistä - ne ovat täsmälleen ( yksinkertaisia ) kärkikolmaan liitettyjä tasograafisia (joissa on vähintään neljä pistettä) [1] [2] . Toisin sanoen mikä tahansa konveksi polytooppi muodostaa 3-liitetyn tasograafin, ja mikä tahansa 3-kytkentäinen tasograafi voidaan esittää konveksina polytooppina. Tästä syystä 3-liitettyjä tasokaavioita kutsutaan myös monitahoisiksi [3] .
Steinitzin lause on nimetty Ernst Steinitzin mukaan, joka julkaisi ensimmäisen todisteen tästä tuloksesta vuonna 1916 [4] . Branko Grünbaum kutsui tätä lausetta "tärkeimmäksi ja syvimmäksi tulokseksi 3-ulotteisen polyhedran suhteen " [2] .
Nimi "Steinitzin lause" soveltuu myös muihin Steinitzin tuloksiin:
Suuntamaton graafi on piste- ja reunajärjestelmä, jossa jokainen reuna yhdistää kaksi kärkeä . Graafi voidaan muodostaa mistä tahansa monitahoista, jos graafin kärjet ovat monitahoisen kärjet ja graafin kaksi kärkeä on yhdistetty reunalla, jos polyhedronin vastaavat kärjet ovat sen reunojen päätepisteitä. Tämä kuvaaja tunnetaan monitahoisen yksiulotteisena luurankona .
Graafi on tasomainen , jos sen kärjet voidaan sijoittaa tasolle ja graafin reunat voidaan piirtää tälle tasolle näitä pisteitä yhdistävinä käyrinä siten, että kaksi reunaa ei leikkaa toisiaan ja kärjet ovat sellaisilla käyrillä, jos vain kärki on vastaavan reunan päätepiste. Farin lauseen mukaan voimme olettaa, että käyrät ovat itse asiassa segmenttejä . Graafi on vertex-3-kytketty , jos sen minkä tahansa kahden kärjen poistamisen jälkeen mikä tahansa jäljellä olevien kärkien pari voidaan yhdistää polulla.
Steinitzin lauseen yhteen suuntaan (helppompi todistaa) väite sanoo, että minkä tahansa konveksin polytoopin graafi on tasomainen ja 3-kytketty. Kuten kuvasta näkyy, tasoisuus voidaan esittää Schlegel-diagrammin avulla - jos asetat pistevalonlähteen lähelle yhtä monitahoisen pinnasta ja sijoitat tason toiselle puolelle, monitahoisen reunojen varjot muodostuvat. tasograafi, joka on upotettu tasoon siten, että graafin reunat esitetään segmentteinä. Polytooppigraafin 3-yhteys on erikoistapaus Balinskyn lauseesta , jonka mukaan minkä tahansa k - ulotteisen konveksin polytoopin graafi on k -kytketty [11] .
Väite toisella, monimutkaisemmalla tavalla sanoo, että mikä tahansa tasomainen 3-liittynyt graafi on kuperan monitahoisen graafi.
Voidaan todistaa tiukempi väite Steinitzin lauseesta, että mikä tahansa monitahoinen graafi voidaan toteuttaa kuperaksi monitahoksi, jonka kärjet ovat kokonaislukukoordinaatteja. Steinitzin alkuperäisessä todistuksessa saadut kokonaisluvut ovat kaksinkertaisesti eksponentiaalinen funktio annetun polyhedronin kärkien lukumäärästä. Siten näiden lukujen kirjoittaminen vaatii eksponentiaalisen määrän bittejä [12] . Myöhemmässä tutkimuksessa löydettiin kuitenkin graafin visualisointialgoritmi , joka vaatii vain O( n ) bittiä jokaisesta kärjestä [13] [14] . Voimme lieventää vaatimusta, että kaikki koordinaatit ovat kokonaislukuja, ja antaa koordinaatit siten, että kärkien x - koordinaatit ovat erilaisia kokonaislukuja välillä [0,2 n − 4] ja kaksi muuta koordinaattia ovat reaalilukuja . välissä [0,1] siten, että jokaisen reunan pituus on vähintään yksi, kun taas monitahoisen tilavuus rajoitetaan O( n ) [15] .
Missä tahansa polytooppissa, joka edustaa tiettyä monitahoista graafia G , G :n pinnat ovat täsmälleen G :n syklejä , jotka eivät jaa G :tä kahdeksi komponentiksi. Toisin sanoen G :n pintaa vastaavan syklin poistaminen antaa G :n yhdistetyn aligraafin . Voit määrittää minkä tahansa monitahoisen pinnan muodon etukäteen - jos valitset syklin C , joka ei jaa kuvaajaa osiin, ja järjestät sen kärjet kaksiulotteisen kuperan monikulmion P muotoon , niin on olemassa monitahoinen esitys G , jossa C :tä vastaava kasvo on kongruentti P :n kanssa [16] . Tietylle monitahograafille G ja mielivaltaiselle syklille C on myös aina mahdollista löytää realisaatio, jossa C muodostaa realisaatiosiluetin rinnakkaisen projektion alla [17] .
Köbe-Andreev- Thurston - ympyrän pakkauslause voidaan nähdä toisena vahvistuksena Steinitzin teoreemaan, jonka mukaan mikä tahansa 3-liittynyt tasograafi voidaan esittää kuperana monitahoisena siten, että sen kaikki reunat koskettavat samaa yksikköpalloa [18] . Yleisemmin ottaen, jos G on monitahoinen graafi ja K on sileä kolmiulotteinen kupera kappale , voidaan löytää G :n monitahoinen esitys, jossa kaikki reunat koskettavat K :tä [19] .