Tietzesův graf - Tietzes graph - Wikipedia
| Tietzeův graf | |
|---|---|
 Tietzeův graf | |
| Vrcholy | 12 |
| Hrany | 18 |
| Poloměr | 3 |
| Průměr | 3 |
| Obvod | 3 |
| Automorfismy | 12 (D6 ) |
| Chromatické číslo | 3 |
| Chromatický index | 4 |
| Vlastnosti | Krychlový Snark |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Tietzeův graf je neorientovaný kubický graf s 12 vrcholy a 18 hranami. Je pojmenován po Heinrich Franz Friedrich Tietze, který v roce 1910 ukázal, že Möbiusův proužek lze rozdělit na šest oblastí, které se navzájem dotýkají - tři podél hranice pásu a tři podél jeho středové čáry - a tedy grafy, které jsou vložený na pás Möbius může vyžadovat šest barvy.[1] Hraniční segmenty oblastí Tietzeho dělení (včetně segmentů podél hranice samotného Möbiova pásu) tvoří vložení Tietzeho grafu.
Vztah k Petersenovu grafu
Tietzeův graf může být vytvořen z Petersenův graf nahrazením jednoho z jeho vrcholů a trojúhelník.[2][3]Stejně jako graf Tietze tvoří i Petersenův graf hranici šesti vzájemně se dotýkajících oblastí, ale na projektivní rovina spíše než na Möbiově pásu. Pokud jeden vyřízne otvor z tohoto dělení projektivní roviny, obklopující jeden vrchol, obklopený vrchol je nahrazen trojúhelníkem regionálních hranic kolem otvoru, což dává dříve popsanou konstrukci grafu Tietze.
Hamiltonicita
Tietzeho graf i Petersenův graf jsou maximálně nehamiltonovský: nemají žádné Hamiltonovský cyklus, ale libovolné dva nesousedící vrcholy lze spojit hamiltonovskou cestou.[2] Tietzeho graf a Petersenův graf jsou jediné 2-vrchol připojený kubické nehamiltonovské grafy s 12 nebo méně vrcholy.[4]
Na rozdíl od Petersenova grafu Tietzeho graf není hypohamiltonián: odstraněním jednoho ze tří vrcholů trojúhelníku se vytvoří menší graf, který zůstane nehamiltonovský.
Barvení hran a perfektní sladění
Barvení hran Tietzeho graf vyžaduje čtyři barvy; to znamená, že jeho chromatický index je 4. Rovněž lze okraje Tietzeho grafu rozdělit na čtyři párování, ale ne méně.
Tietzeův graf odpovídá části definice a pusť se: je to kubický můstkový graf to není tříbarevné. Někteří autoři však omezují snarks na grafy bez 3 cyklů a 4 cyklů a podle této přísnější definice Tietzeho graf není snark. Tietzeův graf je izomorfní s grafem J3, součást nekonečné rodiny květina snarks představil R. Isaacs v roce 1975.[5]
Na rozdíl od Petersenova grafu lze graf Tietze pokrýt čtyřmi perfektní shody. Tato vlastnost hraje klíčovou roli v důkazu, že testování, zda lze graf pokrýt čtyřmi dokonalými shodami, je NP-kompletní.[6]
Další vlastnosti
Tietzeho graf má chromatické číslo 3, chromatický index 4, obvod 3 a průměr 3. číslo nezávislosti je 5. Jeho skupina automorfismu má řád 12 a je izomorfní s dihedrální skupina D6, skupina symetrií a šestiúhelník, včetně rotací i odrazů. Tato skupina má dvě vrcholy o velikosti 3 a jednu o velikosti 6 na vrcholech, a proto tento graf není vrchol-tranzitivní.
Galerie
The chromatické číslo grafu Tietze je 3.
The chromatický index grafu Tietze je 4.
Graf Tietze má číslo křížení 2 a je 1-planární.
Trojrozměrné zabudování grafu Tietze.
Viz také
- Dürerův graf a Franklinův graf, další dva kubické grafy 12 vrcholů
Poznámky
- ^ Tietze, Heinrich (1910), „Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen“ [Několik poznámek k problému zbarvení mapy na jednostranných površích], DMV Výroční zpráva, 19: 155–159[trvalý mrtvý odkaz ].
- ^ A b Clark, L .; Entringer, R. (1983), „Nejmenší maximálně nehamiltonovské grafy“, Periodica Mathematica Hungarica, 14 (1): 57–68, doi:10.1007 / BF02023582
- ^ Weisstein, Eric W. „Tietze's Graph“. MathWorld.
- ^ Punnim, Narong; Saenpholphat, Varaporn; Thaithae, Sermsri (2007), „Téměř Hamiltonovské kubické grafy“ (PDF), International Journal of Computer Science and Network Security, 7 (1): 83–86
- ^ Isaacs, R. (1975), „Nekonečné rodiny netriviálních trojmocných grafů, které nejsou barvitelné Taitem“, Amer. Matematika. Měsíční, Mathematical Association of America, 82 (3): 221–239, doi:10.2307/2319844, JSTOR 2319844.
- ^ Esperet, L .; Mazzuoccolo, G. (2014), „Na kubických přemostěných grafech, jejichž množinu hran nelze pokrýt čtyřmi dokonalými shody“, Journal of Graph Theory, 77 (2): 144–157, arXiv:1301.6926, doi:10,1002 / jgt.21778, PAN 3246172.