Kreivi Thatta
| Kreivi Thatta | |
|---|---|
| Nimetty | William Thomas Tutt |
| Huiput | 46 |
| kylkiluut | 69 |
| Säde | 5 |
| Halkaisija | kahdeksan |
| Ympärysmitta | neljä |
| Automorfismit | 3 ( ) |
| Kromaattinen numero | 3 |
| Kromaattinen indeksi | 3 |
| Ominaisuudet |
monitahoinen |
| Mediatiedostot Wikimedia Commonsissa | |
Tutta-graafi on esimerkki ei- Hamiltonin kuutioisesta monitahoisesta graafista . Siten se toimii vastaesimerkkinä Taten olettamukselle, jossa oletettiin, että millä tahansa 3-säännöllisellä polytooppilla on Hamiltonin sykli [1] [2] .
Rakennutti William Tutt vuonna 1946 [3] . Myöhemmin löydettiin muita vastaesimerkkejä, jotka useimmiten perustuivat Greenbergin lauseeseen .
Rakentaminen
Tatta-graafi koostuu kolmesta identtisestä osasta, ns. Tatta-fragmenteista. Fragmentilla on se ominaisuus, että siitä lähtevästä kolmesta reunasta yksi on välttämättä läsnä Hamiltonin syklissä missä tahansa graafissa, jossa on tällainen fragmentti. Fragmentin "pakolliset" reunat lähestyvät keskipistettä. Koska mikä tahansa Hamiltonin sykli voi käyttää vain kahta niistä, Hamiltonin sykliä ei ole olemassa.
Tuloksena oleva graafi on 3-kytkentäinen ja tasomainen , joten Steinitzin lauseen mukaan tämä graafi on polytooppigraafi. Kaaviossa on 25 puolta.
Geometrisesti se voidaan saada tetraedristä (jonka jokainen pinta vastaa neljää suurta pintaa, joissa on 9 reunaa, joista kolme on fragmentiparien välissä ja neljäs muodostaa ulkopinnan) leikkaamalla toistuvasti pois kolme sen kärkeä.
Ominaisuudet
- Siinä on 46 kärkeä ja 69 reunaa.
- Kuvaajan kromaattinen luku on 3,
- Kromaattinen indeksi on 3,
- ympärysmitta on 4
- Halkaisija on 8.
- Kaavio on 3-kytkentäinen ja tasomainen . Tästä syystä tämä graafi on Steinitzin lauseen mukaan monitahoisen kuvaaja. (Kasvojen määrä on 25.)
- Tutt-graafin automorfismien ryhmä on , kolmannen kertaluvun syklinen ryhmä .
- Kaavion tunnusomainen polynomi : .
Muunnelmia
Vaikka Tutta-graafi on historiallisesti ensimmäinen 3-säännöllinen ei-Hamiltonin monitahoinen graafi, se ei ole niistä pienin.
- Vuonna 1965 Lederberg löysi graafin, jossa on 38 kärkeä ( Barnett-Bosack-Lederberg -graafi ) [4] [5] ,
- Vuonna 1968 Greenberg rakensi useita vastaesimerkkejä Tate-oletuksesta - Greenberg-graafit, joissa on 42, 44 ja 46 pistettä [6] , ja vuonna 1974 löydettiin kaksi muuta vastaavaa graafia (Faulkner-Yanger-graafit), joissa oli 42 ja 44 pistettä [7] . Vuonna 1988 havaittiin, että on olemassa täsmälleen kuusi ei-Hamiltonin monitahoista graafia, joissa on 38 kärkeä, joissa on ei-triviaaleja kolmen reunan poikkileikkauksia. Ne muodostetaan korvaamalla viisikulmaisen prisman kaksi kärkeä samalla fragmentilla kuin Tuttin esimerkissä [8 ] .
Muistiinpanot
- ↑ P.G. Tait. Listauksen topologia // Philosophical Magazine (5. sarja). - 1884. - T. 17 . - S. 30-46 . . Artikkeli uusintapainos julkaisussa Scientific Papers , Voi. II, s. 85-98.
- ↑ WT Tutte. Hamiltonin piireistä // Journal of the London Mathematical Society. - 1946. - T. 21 , no. 2 . — S. 98–101 . - doi : 10.1112/jlms/s1-21.2.98 .
- ↑ Weisstein, Eric W. Tutten kaavio Wolfram MathWorld -verkkosivustolla .
- ↑ Lederberg, J. "DENDRAL-64: Järjestelmä tietokoneiden rakentamiseen, orgaanisten molekyylien laskemiseen ja merkitsemiseen puurakenteina ja syklisinä kaavioina. Osa II. Syklisten kuvaajien topologia. Väliraportti Ilmailu- ja avaruushallinnolle. Grant NsG 81-60. 15. joulukuuta 1965. [1] Arkistoitu 20. toukokuuta 2014 Wayback Machinessa
- ↑ Weisstein, Eric W. Barnette-Bosák-Lederberg Graph Wolfram MathWorld -verkkosivustolla .
- ↑ E. Ya. Grinberg. Kolmannen asteen tasohomogeeniset graafit ilman Hamiltonin syklejä. // Latvia. matematiikka. vuosikirja. - T. 4 . — s. 51-58. .
- ↑ G. B. Faulkner, D. H. Younger. Ei-Hamiltonin kuutio tasokartat. // Diskreetti matematiikka . - 1974. - T. 7 . - S. 67-74 .
- ↑ D.A. Holton, B.D. McKay. Pienimmillä ei-Hamiltonin 3-liitetyillä kuutiotason tasograafilla on 38 kärkeä // Journal of Combinatorial Theory, Series B. - 1988. - V. 45 , no. 3 . — S. 305–319 . - doi : 10.1016/0095-8956(88)90075-5 .