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 3-regularen
(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 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]

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]