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 eri aspektidest ja uurimine veel jätkub.

Üldised parameetrid[muuda | muuda 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.
  • Karakteristlik polünoom .
  • Kromaatiline polünoom

Regulaarsused ja sümmeetria[muuda | muuda 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 transitiivne ja sümmeetriline. Sellest tuleneb ka nende n-ö tugev regulaars, 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 | muuda 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).

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

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

Kirjandus[muuda | muuda lähteteksti]