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 formula_1 mis kajastab graafi sümmeetriat 
. Graafi formula_2 iga automorfism on ka selle "täiendi" formula_3 automorfism, st formula_4. 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 formula_1 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 formula_6 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 formula_7 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" formula_7 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 formula_7 ametlik nimi on korrapära.
Lähenemiste võrdlemine.
Orbiitide rühmateoreetilise ja struktuurse tuvastamisviiside vahekorrast:
Orbiidid on graafi olulisemaid osiseid, ilma nendeta ei ole graafi struktuur määratav.