Heawoodi graaf

(Ümber suunatud leheküljelt Heawood'i graaf)

Heawoodi graaf on üks 14 tipu ja 21 servaga lihtgraaf, mis Peterseni graafi kõrval on graafiteoorias teine huvitavate sümmeetriaomadustega tuntud kuupgraaf (st 3-valentsregulaarne). Graaf on nimetatud inglise matemaatiku Percy John Heawoodi järgi.

Heawoodi graaf

Üldised parameetrid muuda

  • Diameeter – 3
  • Raadius – 3
  • Automorfismide arv – 336
  • Kromaatiline number – 2
  • Kromaatiline indeks – 3
  • Karakteristlik polünoom –  


Regulaarsused ja sümmeetria muuda

Heawoodi graaf on 3-valentsregulaarne, 3-distantsregulaarne ja 6-vööregulaarne. Kolmevalentseid vööregulaarseid graafe nimetatakse kage’ks (inglise: cage). Iga tipp ja iga serv esineb kahes vöös. Heawoodi graafil on üks tipuorbiit ja üks servaorbiit, st see graaf on tippudest ja servadest transitiivne ehk tugevalt sümmeetriline. Heawoodi graafi sümmeetriamõõt ehk korrapära on 0,766.

Graafi automorfismirühm on PGL2(7).

Muid omadusi muuda

 
Heawoodi graafi servade 3-värving
 
Heawoodi graafi kromaatiline number on 2

Paarisarv vööregulaarsusest tuleneb selle graafi kahealuselisus. Vastavad tipuhulgad moodustavad Heawoodi graafi täiendis kaks (omavahel sidusat, kuid mitte lõikuvat) klikki. Seega on selle 14-tipulise graafi täiend 7-klikkregulaarne.

Kirjandust muuda