Peterseni graaf: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
Uus lehekülg: 'thumb|right|Peterseni graaf thumb|right|Peterseni graafi teistsugune, isomorfne kujutus '''Peterseni graaf''' on üks liht...' |
Resümee puudub |
||
4. rida:
== Ü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:
12. rida:
== 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 [[graafi klikk ja vöö|''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 [[graafi sümmeetria|''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 '''S<sub>5</sub>'''.
== Teisi omadusi ==
Peterseni graaf on ''mitteplanaarne'' 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.
| |||
