Heawoodi graaf

Allikas: Vikipeedia
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). Nimi on sellele omistatud inglise matemaatiku Percy John Heawoodi järgi.

Üldised parameetrid[muuda | redigeeri lähteteksti]

  • Diameeter – 3
  • Raadius – 3
  • Automorfismide arv – 336
  • Kromaatiline number – 2
  • Kromaatiline indeks – 3
  • Karakteristlik polünoom – (x-3) (x+3) (x^2-2)^6


Regulaarsused ja sümmeetria[muuda | redigeeri 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 sümmeetriline ehk tugevalt sümmeetriline. Heawoodi graafi sümmeetriamõõt ehk korrapära on 0,766.

Graafi automorfismirühm on PGL2(7).

Teisi omadusi[muuda | redigeeri lähteteksti]

Heawood’i graafi servade 3-värving
Heawood’i graafi kromaatiline number on 2

Paarisarv vööregulaarsusest tuleneb selle graafi kahealuselisus (kaks sõltumatut tipuhulka). Need 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 | redigeeri lähteteksti]