Heawoodov graf

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search
Heawoodov graf
Heawoodov graf
ImePercy John Heawood
Točke14
Povezave21
Polmer3
Premer3
Notranji obseg6
Avtomorfizem336 (PGL2(7))
Kromatično število2
Kromatični indeks3
Značilnosti3-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]