Graafi sümmeetria

Graafi sümmeetria on graafi tippude ja tipupaaride struktuurne omadus moodustada sümmeetriaklasse ehk orbiite mida ka ekvivalentsus- või transitiivsusklassideks nimetatud on.

Sümmeetriliseks on suunamatute servade aspektist nimetatud ka lihtgraafi kuid graafi sümmeetriaga ei ole sellel asjaolul mingit seost.

Rühmateoreetiline lähenemine 
Suvalist, kuid graafi struktuuri säilitavat tippude transpositsiooni nimetatakse graafi automorfismiks.  Graafi automorfism on graafi isomorfism iseendasse. Graafi kõikide automorfismide hulk moodustab permutatsioonide järjestikuse rakendamise mõttes rühma  mis kajastab graafi sümmeetriat 
.  Graafi  iga automorfism on ka selle täiendi  automorfism, st . Iga lõplik rühm on isomorfne mõne graafi automorfismirühmaga .

Automorfismide seisukohalt käsitletakse vaid sidusaid graafe. Automorfismi kasutamine graafis tähendab graafi struktuuri säilitavat tippude ümbernummerdamist. Seda ülesannet peetakse ekvivalentseks isomorfismi tuvastamise ülesandega <ref>В. А. Емеличев и др. Лекции по Теории Графов. Наука, 1990</ref>. Oluline on siin graafi tippude lahutamine rühma  orbiitideks. Graafi nimetatakse transitiivseks kui selle tipud moodustavad ühe orbiidi, sümmeetrilisteks selle servad moodustavad ühe orbiidi ja mitte-transitiivseteks kui selle tipud moodustavad mitu orbiiti.

 Struktuurne lähenemine 
Orbiidid on tuvastatavad ka tipupaaride (süva)identifitseerimise teel. Tipupaaride identifikaatorite (paarimärkide) korrastatud süsteem, graafi semiootiline mudel  tuvastab kõik orbiidid. See on hüpoteetiline kuid töötav meetod J.-T. Tevet. Graafide varjatud külgi. S.E.R.R., Tallinn, 2010 ISBN 9789949213108.

Kõikide orbiitide, st tipu-, serva- ja "mitteserva" orbiitide tuvastamine võimaldab graafide sümmeetriat liigitada järgmiselt:

A. Transitiivsed ehk tippudest sümmeetrilised graafid:
A1. Transitiivne graaf, millel on vaid üks servaorbiit on täissümmeetriline ehk täisgraaf. Kui sellel on vaid üks "mitteserva" orbiit, siis on see samuti täissümmeetriline kuid tühigraaf.
A2. Transitiivne graaf, millel on üks serva- ja üks "mitteserva orbiit" on bisümmeetriline. Näiteks, Peterseni graaf on bisümmeetriline.
A3. Transitiivne graaf, millel on üks serva- ja mitu "mitteserva orbiiti" on servadest sümmeetriline. Näiteks Heawoodi graaf on servadest sümmeetriline. Selle graafi täiend on "mitteservadest" sümmeetriline.
A4. Transitiivset graaf, millel on mitu serva- ja mitu "mitteserva" orbiiti on polüsümmeetriline. Transitiivsete hulgas moodustavad need enamuse.

B. Mittetransitiivsed graafid:
B1. Graaf, millel on rohkem kui üks tipuorbiit on ositi sümmeetriline. Kõikide graafide hulgas moodustavad need enamuse.
B2. Graaf, mille tipuorbiitide arv võrdub tippude arvuga on 0-sümmeetriline ehk asümmeetriline.

Graafi sümmeetria on mõõdetav. Graafi sümmeetria mõõt  sõltub tipupaaride arvust, orbiitide võimsusest ja nende infomahust ning selle väärtus on 0 ja 1 vahel. See loob võimaluse võrrelda, järjestada ja rühmitada  väärtuse järgi erineva suurusega graafe. Sümmeetria väärtus on 1, kui esineb üksainus orbiit ning selle väärtus on 0, kui orbiitide arv võrdub elementide arvuga. Näiteks, Peterseni graafi sümmeetriamõõt on 0,8328, Heawoodi graafil 0,7655. Olenevalt graafist võib mõne mittetransitiivse ositi sümmeetrilise graafi sümmeetriamõõt olla suurem kui transitiivsel polüsümmeetrilisel graafil. Mõõdu  ametlik nimi on korrapära.

 Lähenemiste võrdlemine 
Orbiitide rühmateoreetilise ja struktuurse tuvastamisviiside vahekorrast:
 Rühmateoreetiline lähenemine uurib graafi rühma  sümmeetriat, struktuurne aga graafi  enda sümmeetriat,
 Nii rühmateoreetiliselt kui ka struktuurselt tuvastatud orbiidid langevad kokku''.
 Erinevate struktuuridega (st mitteisomorfsed) graafid võivad omada üht ja sama rühma  (st ühesuguseid sümmeetriaomadusi), kuid nende struktuursed mudelid  on erinevad.
 Rühmateoreetilise orbiidituvastuse korral võib sümmeetriliste graafide puhul permutatsioonide arv (st tipupaaride loend) küündida faktoriaalini!, struktuurne tuvastus piirdub vaid tipupaaride identifitseerimisega.
 Rühmateoreetilise orbiidituvastuse korral tehakse seda tippude ja servade jaoks eraldi ning "mitteserva orbiite" ei tunta. Struktuurne mudel  tuvastab tipu-, serva- ja "mitteserva" orbiidid kompleksselt.
 Tänapäevani peetakse graafi orbiidi tuvastamist rühmateooria valdkonda kuuluvaks ning graafiteoreetikud pole sellele erilist tähelepanu osutanud. Struktuursest seisukohalt on see aga üks kesksemaid probleeme .

Orbiidid on graafi olulisemaid osiseid, ilma nendeta ei ole graafi struktuur määratav.

Vaata ka
Graafi orbiit
Graafide identifitseerimine

Viited 

Rühmateooria
Graafiteooria