Hrabě Thatta
| Hrabě Thatta | |
|---|---|
| Pojmenoval podle | William Thomas Tutt |
| Vrcholy | 46 |
| žebra | 69 |
| Poloměr | 5 |
| Průměr | osm |
| obvod | čtyři |
| Automorfismy | 3 ( ) |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Vlastnosti |
mnohostěnný |
| Mediální soubory na Wikimedia Commons | |
Tuttův graf je příkladem nehamiltonovského kubického polyedrického grafu . Slouží tedy jako protipříklad k Tateově domněnce, která předpokládala, že jakýkoli 3-pravidelný polytop má Hamiltonův cyklus [1] [2] .
Postaven Williamem Tuttem v roce 1946 [3] . Později byly nalezeny další protipříklady, ve většině případů založené na Greenbergově teorému .
Konstrukce
Tatta graf se skládá ze tří stejných kusů, tzv. Tatta fragmentů. Fragment má tu vlastnost, že ze tří hran, které z něj vycházejí, je jedna nutně přítomna v hamiltonovském cyklu v každém grafu s takovým fragmentem. "Požadované" okraje fragmentu se přibližují k centrálnímu vrcholu. Protože každý hamiltonovský cyklus může používat pouze dva z nich, neexistuje žádný hamiltonovský cyklus.
Výsledný graf je 3-souvislý a rovinný , takže podle Steinitzovy věty je tento graf polytopovým grafem. Graf má 25 ploch.
Geometricky jej lze získat z čtyřstěnu (každá plocha odpovídá čtyřem velkým plochám s 9 hranami, z nichž tři jsou mezi páry úlomků a čtvrtá tvoří vnější plochu) opakovaným odříznutím tří jeho vrcholů.
Vlastnosti
- Má 46 vrcholů a 69 hran.
- chromatické číslo grafu je 3,
- chromatický index je 3,
- obvod je 4
- Průměr je 8.
- Graf je 3-souvislý a rovinný . Podle Steinitzova teorému je tedy tento graf grafem mnohostěnu. (Počet obličejů je 25.)
- Skupina automorfismů Tuttova grafu je , cyklická grupa třetího řádu.
- Charakteristický polynom grafu: .
Variace
Přestože je Tuttův graf historicky prvním 3-běžným nehamiltonovským polyedrickým grafem, není z nich nejmenší.
- V roce 1965 Lederberg našel graf s 38 vrcholy ( Barnett-Bosack-Lederberg graph ) [4] [5] ,
- V roce 1968 vytvořil Greenberg několik dalších protipříkladů pro Tateovu domněnku - Greenbergovy grafy se 42, 44 a 46 vrcholy [6] a v roce 1974 byly nalezeny další dva takové grafy (Faulkner-Yangerovy grafy) se 42 a 44 vrcholy [7] . V roce 1988 bylo zjištěno, že existuje přesně šest nehamiltonských polyedrických grafů s 38 vrcholy, které mají netriviální řezy tří hran, jsou vytvořeny nahrazením dvou vrcholů pětibokého hranolu stejným fragmentem, jaký byl použit v Tuttově příkladu [8 ] .
Poznámky
- ↑ P.G. Tait. Listing's Topology // Filosofický časopis (5. s.). - 1884. - T. 17 . — S. 30–46 . . Článek přetištěn ve Scientific Papers , sv. II, str. 85-98.
- ↑ WT Tutte. O hamiltonovských okruzích // Journal of the London Mathematical Society. - 1946. - T. 21 , čís. 2 . — S. 98–101 . - doi : 10.1112/jlms/s1-21.2.98 .
- ↑ Weisstein, Eric W. Tutte 's Graph na webu Wolfram MathWorld .
- ↑ Lederberg, J. „DENDRAL-64: Systém pro konstrukci počítače, počítání a zápis organických molekul jako stromových struktur a cyklických grafů. Část II. Topologie cyklických grafů. Průběžná zpráva pro Národní úřad pro letectví a vesmír. Grant NsG 81-60. 15. prosince 1965. [1] Archivováno 20. května 2014 na Wayback Machine
- ↑ Weisstein, Eric W. Barnette-Bosák-Lederberg Graph na webu Wolfram MathWorld .
- ↑ E. Ya Grinberg. Rovinné homogenní grafy třetího stupně bez hamiltonovských cyklů. // Latv. matematika. ročenka. - T. 4 . — s. 51-58. .
- ↑ G. B. Faulkner, D. H. Younger. Nehamiltonské kubické rovinné mapy. // Diskrétní matematika . - 1974. - T. 7 . - S. 67-74 .
- ↑ D.A. Holton, B.D. McKay. Nejmenší nehamiltonovské 3-spojené kubické rovinné grafy mají 38 vrcholů // Journal of Combinatorial Theory, Series B. - 1988. - V. 45 , no. 3 . — S. 305–319 . - doi : 10.1016/0095-8956(88)90075-5 .