Tietze grafikon
| Tietze grafikon | |
|
A Tietze grafikon ábrázolása. | |
| Csúcsok száma | 12. |
|---|---|
| Élek száma | 18. |
| Fokozat eloszlás | 3- rendszeres |
| Sugár | 3 |
| Átmérő | 3 |
| Háló | 3 |
| Automorfizmusok | 12. ( D 6 ) |
| Kromatikus szám | 3 |
| Kromatikus index | 4 |
| Tulajdonságok |
Köbös Snark |
A Tietze gráf a gráfelméletben egy 3 szabályos gráf , 12 csúcsú és 18 élű. Különösen figyelemre méltó színező tulajdonságai miatt.
Általános tulajdonságok
Általános tulajdonságok
A Tietze gráf átmérője , csúcsainak maximális excentricitása 3, sugara , csúcsainak legkisebb excentricitása 3, hálója , legrövidebb ciklusának hossza pedig 3. Háromcsúcsú -csatolt gráf és egy három éllel összekapcsolt gráf , vagyis hogy összekapcsolt, és hogy szétkapcsolódáshoz legalább 3 csúcstól vagy 3 éltől kell megfosztani.
Színezés
A Tietze gráf kromatikus száma 3, azaz 3 színnel színezhető úgy, hogy egy él által összekötött két csúcs mindig különböző színű legyen, de ez a szám minimális. Nincs érvényes 2 színű grafikon.
A Tietze gráf kromatikus indexe 4. Ezért a grafikon szélei 4-színűek, így az ugyanazon csúcsra eső két él mindig különböző színű. Ez a szám minimális.
Algebrai tulajdonságok
A csoport a automorfizmusainak a Tietze gráf egy csoportja érdekében 12 izomorf az diédercsoport D 6 , a csoport a isometries a sík vezetése szabályos hatszög . Ez a csoport 6 elemből áll, amelyek megfelelnek a forgatásoknak, és 6 további elemnek , amelyek a tükröződéseknek felelnek meg .
A karakterisztikus polinomja a szomszédsági mátrix a Tietze grafikon: .
Merülés a tóruszon és színezés
A Tietze gráf egy tóruszra vethető . A gráf arcainak ekkor megvan az a tulajdonságuk, hogy mindkettő megérinti egymást. Ennek az a következménye, hogy a tóruson egy süllyeszthető gráf színezéséhez hat színre lehet szükség, ami ellentétben áll a négy színű téttel a sík gráfok esetében .
Megjegyzések és hivatkozások
- Heinrich Tietze , „ Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen ” [„Néhány megjegyzés a térkép színezésének problémájához az egyoldalú felületeken”], DMV Éves jelentés , vol. 19, 1910, P. 155-159 ( online olvasás ).
Lásd is
Belső linkek
Külső linkek
- (en) Eric W. Weisstein , a Tietze grafikonja ( MathWorld )