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