Teorema lui Greenberg
Teorema lui Greenberg este o condiție necesară pentru ca un grafic plan să conțină un ciclu hamiltonian bazat pe lungimile ciclului fețelor. Rezultatul este utilizat pe scară largă pentru a construi grafice non-Hamiltoniene cu proprietăți suplimentare. De exemplu, noi contraexemple au fost construite pentru conjectura Tate (pe care Tutt a respins -o în 1946). Teorema a fost demonstrată de matematicianul leton Emanuel Grinberg în 1968.
Formulare
Fie G un grafic planar finit cu un ciclu hamiltonian C cu o încorporare plană fixă. Notăm cu ƒ k și g k numărul de fețe k -gonale ale înglobării care se află în interiorul și respectiv în exteriorul C . Apoi
Această formulă este o consecință simplă a formulei lui Euler .
Un corolar al acestei teoreme este că, dacă un graf plan poate fi încorporat în așa fel încât toate fețele, cu excepția uneia, sunt congruente cu 2 modulo 3 și o față nu este egală cu 2 mod 3, atunci graficul nu este hamiltonian. De exemplu, în graficul din figură, toate fețele au 5 sau 8 laturi, iar fața exterioară are 9 laturi, deci satisface condiția teoremei și, prin urmare, nu este hamiltoniană. Pentru orice graf plan, fețele în care numărul de laturi este congruent cu 2 modulo 3 dau 0 modulo 3 sumei din teorema lui Greenberg, deoarece factorul k - 2 din suma lor dispare. Cu toate acestea, celelalte fețe dau o valoare care este diferită de zero modulo 3, indiferent dacă sunt în interiorul sau în afara ciclului hamiltonian. Și dacă există o singură astfel de față, suma totală nu poate fi zero, iar graficul trebuie să fie non-Hamiltonian.
Aplicații
Greenberg și-a folosit teorema pentru a găsi grafice poliedrice cubice non-Hamiltoniene cu conectivitate ciclică mare. Conectivitatea ciclică a muchiei unui grafic este cel mai mic număr de muchii care pot fi eliminate, astfel încât graficul rămas să conțină mai mult de o componentă ciclică. Graficul Tutta cu 46 de vârfuri și graficele poliedrice cubice mai mici non-Hamiltoniene derivate din acesta au o conexiune ciclică de margine de trei. Greenberg și-a folosit teoria pentru a găsi un graf poliedric cubic non-Hamiltonian cu 44 de vârfuri, 24 de fețe și o conexiune ciclică de margine de patru, precum și un alt exemplu (prezentat în figură) cu 46 de vârfuri, 25 de fețe și o conexiune ciclică de muchie de cinci, conexiunea de margine maximă posibilă pentru graficele plane cubice, altele decât K 4 . În exemplul de mai sus, toate fețele mărginite au cinci sau opt muchii, în ambele cazuri numărul de fețe este congruent cu 2 modulo 3, dar fața exterioară are nouă muchii, ceea ce oferă o contribuție diferită de zero la formula din teorema lui Greenberg modulo. 3. Astfel, graficul nu poate fi hamiltonian.
Teorema lui Greenberg este de asemenea folosită pentru a găsi grafuri planare hipo-Hamiltoniene , din nou prin construirea unui graf în care toate fețele au un număr de muchii congruent cu 2 modulo 3 [1] [2] . Thomassen [3] a folosit teorema într-un mod puțin mai complicat pentru a găsi un grafic hipohamiltonian cubic plan - graficul pe care l-a construit includea o față cu 4 muchii adiacentă unei fețe cu 7 muchii, iar toate celelalte fețe aveau cinci sau opt muchii. Pentru ca graficul să satisfacă teorema lui Greenberg, una dintre fețele cu 4 sau 7 muchii ar trebui să fie separată de celelalte patru, ceea ce este imposibil.
Restricții
Există grafice plane non-Hamiltoniene în care toate fețele au cinci sau opt laturi. Pentru aceste grafice, formula lui Greenberg, luată modulo trei, satisface întotdeauna orice împărțire a fețelor în două submulțimi, ceea ce împiedică utilizarea teoremei pentru a demonstra non-Hamiltonianitatea în acest caz ( Zaks 1977 ).
Este imposibil să folosiți teorema lui Greenberg pentru a găsi contraexemple pentru conjectura lui Barnett că orice graf poliedric bipartit cubic este hamiltonian. În aceste grafice, există întotdeauna o împărțire a fețelor în două submulțimi care satisface teorema lui Greenberg, indiferent dacă aceasta este hamiltoniană ( Krooss 2004 ).
Note
Literatură
- E. Ya. Grinberg. Grafice plane omogene de gradul trei fără cicluri hamiltoniene. // Latv. matematica. anuar. - T. 4 . - S. 51-58. .
- Andre Krooss. Die Barnette'sche Vermutung und die Grinberg'sche Formel (germană) // Analele Universităţii din Craiova. Seria Mathematica-Informatica. - 2004. - Bd. 31 . — S. 59–65 .
- Joseph Malkevitch. Formula poliedrică a lui Euler: Partea a II-a . - Societatea Americană de Matematică , 2005. - (Feature Column).
- Carsten Thomassen. Grafice hipohamiltoniene și hipotrasabile plane și infinite // Matematică discretă . - 1976. - T. 14 , nr. 4 . — S. 377–389 . - doi : 10.1016/0012-365X(76)90071-6 .
- Carsten Thomassen. Grafice cubice planare hipo-hamiltoniene și hipotraceabile // Journal of Combinatorial Theory . - 1981. - T. 30 , nr. 1 . — p. 36–44 . - doi : 10.1016/0095-8956(81)90089-7 .
- Gabor Wiener, Makoto Araya. Întrebarea supremă . - 2009. - arXiv : 0904.3012 .
- WT Tutte . Capitolul 2: Knights Errant // Teoria grafurilor așa cum am cunoscut-o. - New York: The Clarendon Press Oxford University Press, 1998. - V. 11. - (Oxford Lecture Series in Mathematics and its Applications). - ISBN 0-19-850251-6 .
- Joseph Zaks. Grafice non-Hamiltoniene non-Grinbergiene // Matematică discretă . - 1977. - T. 17 , nr. 3 . — S. 317–321 . - doi : 10.1016/0012-365X(77)90165-0 .