Peterseni graaf

Allikas: Vikipeedia
Peterseni graaf
Peterseni graafi teistsugune, isomorfne kujutus

Peterseni graaf on üks lihtne kuid huvitavate omadustega regulaarne graaf, mille konstrueeris 1898. aastal Taani matemaatik Julius Petersen kontranäitena ühele tollasele regulaarseid graafe puudutavale teoreemile. Selle graafi omadusi on uuritud väga erinevatest aspektidest ning see ei ole veel lõppenud.

Üldised parameetrid[muuda | redigeeri lähteteksti]

Peterseni graaf on harilik (st mittesuunatud) kuupgraaf (st 3-valentsregulaarne). See 10-tipuline ja 15 servaga graaf on konstrueeritav kui 5-täisgraafi servagraafi täiend. Selle kromaatiline arv on 3, kromaatiline klass 4, st ei kujuta endast kolme 1-faktori summat.

Peterseni graafi:

  • Spekter on −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
  • Karateristlik polünoom (t-1)^5(t+2)^4(t-3).
  • Kromaatiline polünoom t(t - 1)(t - 2)(t^7 - 12t^6 + 67t^5 -
    230t^4 + 529t^3 - 814t^2 + 775t - 352)

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

Peterseni graaf on 3-valentsregulaarne, 2-distantsregulaarne ja 5-vööregulaarne. Kolmevalentseid vööregulaarseid graafe nimetatakse kage’ks (inglise: cage). Peterseni graafis on kaksteist 5-vööd. Iga tipp esineb 6 vöös ja iga serv esineb 4 vöös.

Peterseni graafi 'täiend' on 4-klikkregulaarne, selles on viis lõikuvat 4-klikki. Iga tipp esineb kahes klikis ja iga serv esineb ühes klikis.

Peterseni graaf ja selle täiend on transitiivsed, (serv)sümmeetrilised ja bisümmeetrilised. Need mõlemad on ka tugevalt regulaarsed, mis antud juhul tuleneb otseselt nende bisümmeetriast (kõik bisümmeetrilised graafid on tugevregulaarsed, kuid mitte vastupidi).

Graafi automorfismirühm on S5.

Teisi omadusi[muuda | redigeeri lähteteksti]

Peterseni graafi servade 4-värving
Peterseni graafi tippude 3-värving

Peterseni graaf on mittetasandiline ja hüpohamiltonlik See graaf on seotud värvitavuse probleemiga (inglise: vertex and edge colouring). Räägitakse Peterseni fenomenist ja Peterseni perekonnast graafides. Viimase puhul on püütud konstrueerida 14-, 18-, … tipulisi graafe, mis säilitavad 5-vööregulaarsuse (kuid ei säilita bisümmeetriat).

Petrseni graafi, nagu mõnda teistki on uuritud erinevate inimeste poolt väga spetsiifilistest külgedest. Kokkuvõtvat kirjutist sellest ei leidu. Üks kokkuvõtlikumaid suundi näitavaid artikleid sellest on inglise Wikipedia’s.


Graafi struktuuri ja sümmeetriaomaduste uurimiseks sobivad nende semiootilised mudelid.

Kirjandust[muuda | redigeeri lähteteksti]