Contele Thatta
| Contele Thatta | |
|---|---|
| Numit după | William Thomas Tutt |
| Vârfurile | 46 |
| coaste | 69 |
| Rază | 5 |
| Diametru | opt |
| Circumferinţă | patru |
| Automorfisme | 3 ( ) |
| Număr cromatic | 3 |
| Indicele cromatic | 3 |
| Proprietăți |
poliedrică |
| Fișiere media la Wikimedia Commons | |
Graficul Tutta este un exemplu de grafic poliedric cubic non- Hamiltonian . Astfel, servește ca un contraexemplu pentru conjectura lui Tate , care presupunea că orice politop 3-regular are un ciclu hamiltonian [1] [2] .
Construită de William Tutt în 1946 [3] . Ulterior, au fost găsite și alte contraexemple, în majoritatea cazurilor bazate pe teorema Greenberg .
Clădire
Graficul Tatta este format din trei piese identice, așa-numitele fragmente Tatta. Un fragment are proprietatea că dintre cele trei muchii care ies din el, una este neapărat prezentă în ciclul hamiltonian în orice graf cu un astfel de fragment. Marginile „necesare” ale fragmentului se apropie de vârful central. Deoarece orice ciclu hamiltonian poate folosi doar două dintre ele, nu există un ciclu hamiltonian.
Graficul rezultat este 3-conectat și plan , deci, după teorema lui Steinitz, acest grafic este un graf politop. Graficul are 25 de fețe.
Din punct de vedere geometric, poate fi obținut dintr-un tetraedru (fiecărei fețe îi corespunde patru fețe mari cu 9 muchii, dintre care trei sunt între perechi de fragmente, iar a patra formează fața exterioară) prin tăierea în mod repetat a trei dintre vârfurile sale.
Proprietăți
- Are 46 de vârfuri și 69 de muchii.
- Numărul cromatic al graficului este 3,
- Indicele cromatic este 3,
- circumferinta este 4
- Diametrul este de 8.
- Graficul este 3-conectat și plan . Prin urmare, după teorema Steinitz , acest grafic este un grafic al unui poliedru. (Numărul de fețe este 25.)
- Grupul de automorfisme ale grafului Tutt este , un grup ciclic de ordinul trei.
- Polinomul caracteristic al graficului: .
Variante
Deși graficul Tutta este din punct de vedere istoric primul graf poliedric ne-Hamiltonian cu 3 regulate, nu este cel mai mic dintre ele.
- În 1965, Lederberg a găsit un grafic cu 38 de vârfuri (graful Barnett-Bosack-Lederberg ) [4] [5] ,
- În 1968, Greenberg a mai construit câteva contraexemple pentru conjectura Tate - grafice Greenberg cu 42, 44 și 46 de vârfuri [6] , iar în 1974 au fost găsite încă două astfel de grafice (grafice Faulkner-Yanger) cu 42 și 44 de vârfuri [7] . În 1988, s-a constatat că există exact șase grafice poliedrice non-Hamiltoniene cu 38 de vârfuri având secțiuni netriviale de trei muchii, acestea fiind formate prin înlocuirea a două vârfuri ale unei prisme pentagonale cu același fragment ca în exemplul lui Tutt [8] ] .
Note
- ↑ P.G. Tait. Topologia Listingului // Revista Filosofică (ser. a 5-a). - 1884. - T. 17 . — S. 30–46 . . Articol retipărit în Scientific Papers , Vol. II, pp. 85-98.
- ↑ WT Tutte. Despre circuitele hamiltoniene // Journal of the London Mathematical Society. - 1946. - T. 21 , nr. 2 . — S. 98–101 . - doi : 10.1112/jlms/s1-21.2.98 .
- ↑ Weisstein, Graficul lui Eric W. Tutte pe site-ul Wolfram MathWorld .
- ↑ Lederberg, J. „DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Partea a II-a. Topologia graficelor ciclice. Raport intermediar către Administrația Națională pentru Aeronautică și Spațiu. Grant NsG 81-60. 15 decembrie 1965. [1] Arhivat 20 mai 2014 la Wayback Machine
- ↑ Weisstein, Eric W. Barnette-Bosák-Lederberg Graph pe site- ul Wolfram MathWorld .
- ↑ E. Ya. Grinberg. Grafice plane omogene de gradul trei fără cicluri hamiltoniene. // Latv. matematica. anuar. - T. 4 . — p. 51-58. .
- ↑ G. B. Faulkner, D. H. Younger. Hărți planare cubice non-Hamiltonian. // Matematică discretă . - 1974. - T. 7 . - S. 67-74 .
- ↑ D.A. Holton, B.D. McKay. Cele mai mici grafuri planare cubice cu 3 conexiuni non-Hamiltoniene au 38 de vârfuri // Journal of Combinatorial Theory, Series B. - 1988. - V. 45 , nr. 3 . — S. 305–319 . - doi : 10.1016/0095-8956(88)90075-5 .