| Tietze gróf | |
|---|---|
| Valaki után elnevezve | Heinrich Tietze |
| Csúcsok | 12 |
| borda | tizennyolc |
| Sugár | 3 |
| Átmérő | 3 |
| Heveder | 3 |
| Automorfizmusok | 12 ( D6 ) |
| Kromatikus szám | 3 |
| Kromatikus index | négy |
| Tulajdonságok |
Cubic Snark |
| Médiafájlok a Wikimedia Commons oldalon | |
A gráfelméletben a Tietze-gráf egy irányítatlan köbös gráf , amelynek 12 csúcsa és 18 éle van. A gráf Heinrich Tietze nevéhez fűződik , aki 1910-ben kimutatta, hogy egy Möbius-csík hat egymást érintő területre osztható – három a csík széle mentén és három a középvonal mentén –, tehát hat színre lehet szükség olyan gráfokhoz, amelyek Möbius-szalagba ágyazható [1] . A Möbius-csík felosztásának Tietze-tartományainak határszegmensei (beleértve a sáv határa mentén lévő szegmenseket is) a Tietze-gráf beágyazottságát alkotják.
A Tietze-gráfot a Petersen-gráfból úgy kaphatjuk meg, hogy az egyik csúcsát egy háromszögre cseréljük [2] . A Tietze-gráfhoz hasonlóan a Petersen-gráf is hat egymást érintő tartomány határaként szolgál, de a projektív síkban , nem pedig a Möbius-sávon. Ha kivágjuk a projektív sík ezen partíciójának valamelyik csúcsának környékét, akkor a csúcsot ennek a furatnak a határaira cseréljük, ami pontosan megadja a fent leírt Tietze-gráf konstrukcióját.
A Tietze-gráf és a Peterson-gráf is maximálisan nem Hamilton- gráf - nincs Hamilton-ciklusa , de bármely két nem szomszédos csúcs összekapcsolható Hamilton-úttal [2] . A Tietze-gráf és a Petersen -gráf az egyetlen 2 csúcshoz kapcsolódó nem Hamilton-köbös gráf, amelynek legfeljebb 12 csúcsa van [3] .
A Petersen-gráftól eltérően a Tietze-gráf nem hipo -Hamilton-gráf – a háromszög három csúcsa közül az egyik eltávolítása egy kisebb gráfot eredményez, amely nem Hamilton-féle marad.
A Tietze-gráf éleinek színezéséhez négy színre van szükség, így a kromatikus indexe 4. Ez egyenértékű azzal, hogy a Tietze-gráf éleit fel lehet osztani négy illesztésre , de nem kevesebbre.
A Tietze-gráf kielégíti a snark definíciójának követelményeinek egy részét - ez egy köbös gráf hidak nélkül , és élei nem lehetnek háromszínűek. Egyes szerzők azonban a snarkot 3- és 4-ciklus nélküli gráfokra korlátozzák, és ilyen erősebb feltételek mellett a Tietze-gráf nem snark. A Tietze-gráf izomorf a J 3 gráfhoz, amely a R. Isaacs által 1975-ben javasolt "Virág" snarkok végtelen családjából származik [4] .
A Petersen-gráftól eltérően a Tietze-gráf négy tökéletes illeszkedéssel fedhető le . Ez a tulajdonság kulcsszerepet játszik annak bizonyításában, hogy annak ellenőrzése, hogy egy gráf lefedhető-e négy illesztéssel, NP-teljes probléma [5] .
A Tietze-gráf kromatikus száma 3, kromatikus indexe 4, kerülete 3, átmérője 3. Függetlenségi száma 5, automorfizmuscsoportja 12-es rendű, és izomorf a D 6 diédercsoporttal , a hatszög szimmetriacsoportjával , amely magában foglalja a forgásokat és a tükröződéseket is. Ez a csoport két 3-as és egy 6-os méretű pályát tartalmaz a csúcsokban, ezért ez a gráf nem csúcstranzitív .
A Tietze-gráf kromatikus száma 3.
A Tietz-gráf kromatikus indexe 4.
A Tietze-gráf metszéspontja 2, és 1-síkú .
A Tietze-gráf háromdimenziós beágyazása.