Peterseni graaf

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.

Peterseni graaf

Peterseni graafi teistsugune, isomorfne kujutus

Üldised parameetrid

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 ${\displaystyle (t-1)^{5}(t+2)^{4}(t-3)}$.
• Kromaatiline polünoom ${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-}$
  ${\displaystyle 230t^{4}+529t^{3}-814t^{2}+775t-352)}$

Regulaarsused ja sümmeetria

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 S₅.

Teisi omadusi

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

• J. A. Bondy, U. S. R. Murty. 2008. Graph Theory. Springer, ISBN 9781846289699.
• J.-T. Tevet. 2010. Graafide varjatud külgi. SERR, ISBN 9789949213108.
• A. Dharwadker, B. Pirzada. 2011. Graph Theory. Amazon Books, ISBN 9781466254992.