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
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 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.

SkliciUredi

  1. Brouwer, Andries Evert. "Heawood graph". Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989). Označba za poševno ali poudarjeno pisavo ni dovoljena v: |work= (pomoč); Zunanja povezava v |work= (pomoč)
  2. Brown (2002).
  3. Heawood (1890).

ViriUredi

Zunanje povezaveUredi