Heawoodi graaf

Allikas: Vikipeedia
Heawoodi 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.

Üldised parameetrid[muuda | muuda lähteteksti]

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


Regulaarsused ja sümmeetria[muuda | muuda lähteteksti]

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 | muuda lähteteksti]

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 | muuda lähteteksti]