Contele de Heawood

Graficul Heawood  este un grafic nedirecționat cu 14 vârfuri și 21 de muchii, numit după Percy John Heawood [1] .

Proprietăți combinatorii

Graficul este cubic și toate ciclurile din grafic conțin șase sau mai multe muchii. Orice grafic cubic mai mic conține cicluri mai mici, deci acest grafic este o celulă (3,6) , cel mai mic grafic cubic cu circumferința 6. Este, de asemenea , tranzitiv la distanță (vezi lista lui Foster ), și, prin urmare , regulat la distanță [2] . Există 24 de potriviri în graficul Heawood și, în toate potrivirile, muchiile care nu sunt incluse în potrivire formează un ciclu hamiltonian . De exemplu, figura prezintă vârfuri de grafic plasate pe un cerc și formând un ciclu, iar diagonalele din interiorul cercului formează o potrivire. Dacă împărțim marginile ciclului în două potriviri, obținem trei potriviri perfecte (adică o colorare în trei culori a marginilor ) în opt moduri diferite [2] . Datorită simetriei graficului, oricare două potriviri perfecte și oricare două cicluri hamiltoniene pot fi transformate de la unul la altul [3] .

Graficul Heawood are 28 de cicluri care conțin fiecare șase vârfuri. Fiecare astfel de ciclu nu este exact legat de celelalte trei cicluri cu 6 vârfuri. Printre aceste trei cicluri, fiecare este diferența simetrică a celorlalte două. Un grafic în care fiecare vârf corespunde unui ciclu de 6 vârfuri în graficul Heawood, iar arcele corespund perechilor deconectate este graficul Coxeter [4] .

Proprietăți geometrice și topologice

Graficul Heawood este un graf toroidal , ceea ce înseamnă că poate fi încorporat fără intersecții într-un tor . Un astfel de tip de încorporare plasează vârfurile și muchiile unui grafic în spațiul euclidian tridimensional ca un set de vârfuri și muchii ale unui politop neconvex cu topologie de torus, politopul Silashi . Graficul este numit după Percy John Heawood , care a dovedit în 1890 că șapte culori sunt suficiente pentru a colora orice plăci poligon torus [5] [6] . Graficul Heawood formează o partiție a torusului în șapte regiuni adiacente reciproc, ceea ce arată că granița este exactă. Graficul Heawood este, de asemenea , graficul Levi al planului Fano , adică graficul reprezentând incidența punctelor și a liniilor din această geometrie. În această interpretare, ciclurile de lungime 6 din graficul Heawood corespund triunghiurilor suprafeței Fano. Graficul Heawood are un număr de încrucișări de 3 și este cel mai mic grafic cubic cu acest număr de încrucișări [7] . Împreună cu graficul Heawood, există 8 grafice diferite de ordinul 14 cu un număr de încrucișări de 3. Graficul Heawood este un grafic de unitate de distanță  - poate fi încorporat într-un plan, astfel încât vârfurile adiacente să fie exact la o distanță de unu, în timp ce două vârfuri nu vor cădea pe același loc al planului și niciun punct nu va fi în interiorul muchiei. Cu toate acestea, înglobărilor cunoscute de acest tip le lipsește simetria inerentă unui grafic [8] .

Proprietăți algebrice

Grupul de automorfism al grafului Heawood este izomorf cu grupul liniar proiectiv PGL 2 (7), un grup de ordin 336 [9] . Acționează tranzitiv asupra vârfurilor , muchiilor și arcelor graficului, deci graficul Heawood este simetric . Există automorfisme care duc orice vârf la orice alt vârf și orice muchie la orice altă muchie. Conform listei lui Foster , graficul Heawood, denumit F014A, este singurul grafic cubic cu 14 vârfuri [10] [11] . Polinomul caracteristic al matricei grafice Heawood este . Spectrul graficului este. Acesta este singurul grafic cu un astfel de polinom care este determinat de spectru.

Polinomul cromatic al graficului este:

Galerie

• Poliedrul Silashi .

• Graficul Heawood are 3 încrucișări .

• Indicele cromatic al graficului Heawood este 3.

• Numărul cromatic al graficului Heawood este 2.

• O încorporare a graficului Heawood într-un tor (prezentat ca un pătrat cu condiții periodice la limită ), împărțindu-l în șapte regiuni adiacente reciproc

Note

1. ^ Weisstein, Eric W. Heawood Graph pe site- ul web Wolfram MathWorld .  
2. ↑ 1 2 Brouwer, Andries E. Graficul Heawood . Adăugiri și corecții la cartea „Distance-Regular Graphs” (Brouwer, Cohen, Neumaier; Springer; 1989) . Preluat la 2 ianuarie 2014. Arhivat din original la 1 august 2012. (nedefinit)
3. ↑ M. Abreu, REL Aldred, M. Funk, Bill Jackson, D. Labbate, J. Sheehan. Grafice și digrafe cu toți 2-factori izomorfi // Journal of Combinatorial Theory. - 2004. - T. 92 , nr. 2 . - S. 395-404 . - doi : 10.1016/j.jctb.2004.09.004 . .
4. ↑ Italo J. Dejter. De la graficul Coxeter la graficul Klein // Journal of Graph Theory. - 2011. - doi : 10.1002/jgt.20597 . - arXiv : 1002.1960 . .
5. ↑ Ezra Brown. Numeroasele nume ale (7,3,1) // Revista de matematică . - 2002. - T. 75 , nr. 2 . - S. 83-94 . - doi : 10.2307/3219140 . — .
6. ↑ PJ Heawood. Teoreme de colorare a hărților // Trimestrial J. Math. Oxford Ser. - 1890. - T. 24 . - S. 322-339 .
7. ↑ Secvența OEIS A110507 _
8. ↑ Eberhard H., A. Gerbracht. Unsprezece unități de încorporare de distanță ale graficului Heawood. - 2009. - arXiv : 0912.5395 . .
9. ↑ JA Bondy, USR Murty. Teoria grafurilor cu aplicații . - New York: Olanda de Nord, 1976. - P. 237. - ISBN 0-444-19451-7 .
10. ↑ Royle, G. „Cubic symmetric graphs (lista lui Foster).” Arhivat din original pe 20 iulie 2008.
11. ↑ Marston Conder și Dobcsányi, P. „Trivalent Symmetric Graphs Up to 768 Vertices”. J. Combin. Matematică. Combina. Calculator. 40, 41-63, 2002.