Steinitz tétele egy 3D konvex poliéder élei és csúcsai által alkotott irányítatlan gráfok kombinatorikus leírása - ezek pontosan ( egyszerű ) csúcsú 3-as síkgráfok (legalább négy csúcstal) [1] [2] . Ez azt jelenti, hogy bármely konvex politóp egy 3-összefüggésű síkgráfot alkot, és bármely 3-kapcsolatú síkgráf ábrázolható konvex politópként. Emiatt a 3 összekapcsolt síkgráfokat poliédernek is nevezik [3] .
Steinitz tételét Ernst Steinitzről nevezték el , aki 1916-ban publikálta ennek az eredménynek az első bizonyítékát [4] . Branko Grünbaum ezt a tételt "a háromdimenziós poliéderek legfontosabb és legmélyebb eredményének " nevezte [2] .
A "Steinitz-tétel" elnevezés Steinitz más eredményeire is alkalmazható:
Az irányítatlan gráf csúcsok és élek rendszere , ahol minden él két csúcsot köt össze. Bármely poliéderből képezhető gráf, ha a gráf csúcsait a poliéder csúcsainak vesszük, és a gráf két csúcsát egy él köti össze, ha a poliéder megfelelő csúcsai az éleinek végpontjai. Ez a gráf a poliéder egydimenziós vázaként ismert.
Egy gráf akkor sík , ha a csúcsai egy síkon elhelyezhetők, és a gráf élei ezen a síkon e pontokat összekötő görbékként rajzolhatók meg úgy, hogy két él ne metszi egymást, és a csúcsok ilyen görbéken fekszenek, ha csak a csúcs a megfelelő él végpontja . Fari tétele alapján feltételezhetjük, hogy a görbék valójában szegmensek . Egy gráf 3-as csúcshoz kapcsolódik , ha bármelyik két csúcs eltávolítása után a fennmaradó csúcsok bármelyik párja összeköthető egy útvonallal.
Steinitz tételének egyirányú (könnyebben bizonyítható) állítása azt mondja, hogy bármely konvex politóp gráfja síkbeli és 3-kapcsolatos. Ahogy az ábrán is látható, a síkosság Schlegel-diagram segítségével ábrázolható - ha a poliéder egyik lapja közelébe helyezünk egy pontszerű fényforrást , a másik oldalára pedig egy síkot, akkor a poliéder éleinek árnyékai kialakulnak. sík gráf, amely a síkba van beágyazva oly módon, hogy a gráf élei szegmensekként jelennek meg. A politóp gráf 3-konnektivitása Balinsky tételének egy speciális esete , miszerint bármely k - dimenziós konvex politóp gráfja k - kapcsolt [11] .
Az állítás egy másik, bonyolultabb módon azt mondja, hogy bármely sík 3-összefüggésű gráf egy konvex poliéder gráfja.
Bebizonyíthatjuk Steinitz tételének szigorúbb állítását, miszerint bármely poliéder gráf megvalósítható konvex poliéderként, amelynek csúcsai egész koordinátákkal rendelkeznek. A Steinitz-féle eredeti bizonyításban kapott egész számok az adott poliéder csúcsszámának kétszeresen exponenciális függvényei Így ezeknek a számoknak a felírásához exponenciális számú bitre van szükség [12] . A későbbi kutatások azonban találtak egy gráfvizualizációs algoritmust, amely minden csúcshoz csak O( n ) bitet igényel [13] [14] . Enyhíthetjük azt a követelményt, hogy minden koordináta egész szám legyen, és koordinátákat rendeljünk hozzá úgy, hogy a csúcsok x - koordinátái különböző egészek legyenek a [0,2 n − 4] intervallumban, a másik két koordináta pedig valós szám . a [0,1] intervallumban úgy, hogy minden élnek legalább egy hosszúsága legyen, míg a poliéder térfogata O( n ) -ra korlátozódik [15] .
Bármely politópban, amely egy adott G poliéder gráfot reprezentál, G lapjai pontosan olyan ciklusok G -ben , amelyek nem osztják G -t két komponensre. Vagyis G-ből egy lapnak megfelelő ciklust eltávolítva G összefüggő részgráfját kapjuk . A poliéder bármelyik lapjának alakját előre megadhatja - ha olyan C ciklust választ , amely nem osztja részekre a gráfot, és csúcsait egy kétdimenziós konvex P sokszög alakjában rendezi el , akkor van egy poliéderes G ábrázolás , amelyben a C -nek megfelelő lap kongruens P -vel [16] . Az is mindig lehetséges, hogy egy adott G poliéder gráf és egy tetszőleges C ciklus olyan realizációt találjon, amelyben C párhuzamos vetület alatt realizációs sziluettet alkot [17] .
A Köbe-Andreev- Thurston körcsomagolási tétel a Steinitz-tétel újabb erősítésének tekinthető, amely szerint bármely 3-összefüggésű síkgráf konvex poliéderként ábrázolható oly módon, hogy minden éle ugyanazt az egységgömböt érinti [18] . Általánosabban fogalmazva, ha G egy poliéder gráf, és K egy sima, háromdimenziós konvex test , akkor találhatunk G poliéderes ábrázolását , amelyben minden él érinti K -t [19] .