Heawoodov graf
Heawoodov graf je v teoriji grafov neusmerjeni graf s 14 točkami in 21 povezavami. Graf je 3-regularen (kubičen), vsi cikli v njem pa imajo šest ali več povezav. Vsak manjši kubični graf ima krajše cikle, tako da je ta graf (3,6)-kletka, najmanjši kubični graf z notranjim obsegom enakim 6. Je tudi Levijev graf Fanojeve ravnine, graf, ki predstavlja incidence med točkami in premicami v tej geometriji. Heawoodov graf je razdaljno-regularen; njegova grupa avtomorfizmov je PGL2(7).[1]
Heawoodov graf se imenuje po britanskem matematiku Percyju Johnu Heawoodu, ki je leta 1890 dokazal, da se lahko vsako subdivizijo torusa v mnogokotnike obarva z največ sedmimi barvami.[2][3] Heawoodov graf tvori subdivizijo torusa s sedmimi medsebojno sosedskimi območji, in kaže da je ta vez močna.
Sklici
[uredi | uredi kodo]- ↑ Brouwer, Andries Evert. »Heawood graph«. Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989).
- ↑ Brown (2002).
- ↑ Heawood (1890).
Viri
[uredi | uredi kodo]- Brown, Ezra (2002), »The many names of (7,3,1)« (PDF), Mathematics Magazine, 75 (2): 83–94, doi:10.2307/3219140, JSTOR 3219140, arhivirano iz prvotnega spletišča (PDF) dne 5. februarja 2012, pridobljeno 14. septembra 2010
- Heawood, Percy John (1890), »Map colouring theorems«, Quarterly J. Math. Oxford Ser., 24: 322–339
