Heawoodov graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Heawoodov graf
Heawoodov graf
Ime Percy John Heawood
Točke 14
Povezave 21
Polmer 3
Premer 3
Notranji obseg 6
Avtomorfizem 336 (PGL2(7))
Kromatično število 2
Kromatični indeks 3
Značilnosti kubičen
kletka
razdaljno-prehoden
razdaljno-regularen
toroiden
Hamiltonov
simetričen
z enotsko razdaljo

Heawoodov graf je v teoriji grafov neusmerjeni graf s 14 točkami in 21 povezavami. Graf je 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 lahko vsako subdivizijo torusa v mnogokotnike obarvamo 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.

Opombe in sklici[uredi | uredi kodo]

  1. ^ Brouwer, Andries Evert. "Heawood graph". Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989). 
  2. ^ Brown (2002).
  3. ^ Heawood (1890).

Viri[uredi | uredi kodo]

  • Heawood, Percy John (1890). "Map colouring theorems". Quarterly J. Math. Oxford Ser. 24: 322–339. 

Zunanje povezave[uredi | uredi kodo]