Thatta gróf
| Thatta gróf | |
|---|---|
| Valaki után elnevezve | William Thomas Tutt |
| Csúcsok | 46 |
| borda | 69 |
| Sugár | 5 |
| Átmérő | nyolc |
| Heveder | négy |
| Automorfizmusok | 3 ( ) |
| Kromatikus szám | 3 |
| Kromatikus index | 3 |
| Tulajdonságok |
poliéderes |
| Médiafájlok a Wikimedia Commons oldalon | |
A Tutta-gráf egy nem Hamilton -féle köbös poliéder gráf egy példája . Így ellenpéldaként szolgál Tate sejtésére, amely feltételezi, hogy bármely 3-reguláris politópnak van Hamilton-ciklusa [1] [2] .
William Tutt építette 1946 - ban [3] . Később más ellenpéldákat is találtak, a legtöbb esetben a Greenberg-tétel alapján .
Épület
A Tatta-gráf három egyforma darabból, az úgynevezett Tatta-töredékekből áll. Egy töredéknek megvan az a tulajdonsága, hogy a belőle kilépő három él közül az egyik szükségszerűen jelen van a Hamilton-ciklusban minden ilyen töredéket tartalmazó gráfban. A töredék "szükséges" élei megközelítik a központi csúcsot. Mivel bármelyik Hamilton-ciklus csak kettőt használhat fel, nincs Hamilton-ciklus.
A kapott gráf 3-kapcsolatos és síkbeli , tehát Steinitz tétele szerint ez a gráf egy politóp gráf. A grafikonnak 25 lapja van.
Geometriailag egy tetraéderből (mindegyik lapja négy nagy, 9 éles lapnak felel meg, amelyek közül három töredékpárok között van, a negyedik pedig a külső felületet alkotja) három csúcsának többszöri levágásával.
Tulajdonságok
- 46 csúcsa és 69 éle van.
- A gráf kromatikus száma 3,
- A kromatikus index 3,
- kerülete 4
- Az átmérője 8.
- A grafikon 3-kapcsolatos és síkbeli . Ezért a Steinitz-tétel szerint ez a gráf egy poliéder gráfja. (Az arcok száma 25.)
- A Tutt - gráf automorfizmusainak csoportja harmadrendű ciklikus csoport .
- A gráf karakterisztikus polinomja : .
Változatok
Bár a Tutta-gráf történelmileg az első 3-reguláris nem-Hamilton-féle poliéder gráf, nem a legkisebb közülük.
- 1965-ben Lederberg talált egy 38 csúcsú gráfot ( a Barnett-Bosack-Lederberg gráfot ) [4] [5] ,
- 1968-ban Greenberg még több ellenpéldát épített a Tate-sejtésre – 42, 44 és 46 csúcsú Greenberg-gráfok [6] , 1974-ben pedig további két ilyen gráfot találtak (Faulkner-Yanger gráfok) 42 és 44 csúcsokkal [7] . 1988-ban azt találták, hogy pontosan hat nem Hamilton-féle poliéder gráf van 38 csúcsával, amelyek három él nem triviális szakaszai vannak. Ezeket úgy alakították ki, hogy egy ötszögletű prizma két csúcsát ugyanazzal a töredékre cserélik, mint a Tutt példájában [8 ] .
Jegyzetek
- ↑ P.G. Tait. Listing topológiája // Filozófiai Magazin (5. szer.). - 1884. - T. 17 . – S. 30–46 . . A cikk újranyomtatva a Scientific Papers , Vol. II, pp. 85-98.
- ↑ WT Tutte. A Hamiltoni áramkörökről // A London Mathematical Society folyóirata. - 1946. - T. 21 , sz. 2 . – S. 98–101 . - doi : 10.1112/jlms/s1-21.2.98 .
- ↑ Weisstein , Eric W. Tutte grafikonja a Wolfram MathWorld webhelyen .
- ↑ Lederberg, J. "DENDRAL-64: Rendszer a szerves molekulák, mint faszerkezetek és ciklikus grafikonok számítógépes felépítéséhez, felsorolásához és jelöléséhez. rész II. Ciklikus gráfok topológiája. Időközi jelentés a Nemzeti Repülési és Űrkutatási Hivatalnak. Grant NsG 81-60. 1965. december 15. [1] Archiválva : 2014. május 20. a Wayback Machine -nél
- ↑ Weisstein, Eric W. Barnette-Bosák-Lederberg grafikon a Wolfram MathWorld weboldalán .
- ↑ E. Ya. Grinberg. Harmadik fokú síkhomogén gráfok Hamilton-ciklusok nélkül. // Latv. matematika. évkönyv. - T. 4 . — 51-58. .
- ↑ G. B. Faulkner, D. H. Younger. Nem Hamilton köbös síkbeli térképek. // Diszkrét matematika . - 1974. - T. 7 . - S. 67-74 .
- ↑ D.A. Holton, B.D. McKay. A legkisebb nem Hamilton-féle 3-összefüggõ köbös síkgráfok 38 csúcsúak // Journal of Combinatorial Theory, Series B. - 1988. - V. 45 , no. 3 . – S. 305–319 . - doi : 10.1016/0095-8956(88)90075-5 .