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  {AutG}  mis kajastab graafi sümmeetriat 
.  Graafi  G  iga automorfism on ka selle *täiendi*  \overline G  automorfism, st  {AutG} = {Aut}\overline G. 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  {AutG}  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  S  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***  SR  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*  SR  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  SR  ametlik nimi on ***korrapära***.

## Lähenemiste võrdlemine
Orbiitide rühmateoreetilise ja struktuurse tuvastamisviiside vahekorrast:
* Rühmateoreetiline lähenemine uurib graafi rühma  {AutG}  sümmeetriat, struktuurne aga graafi  G  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  {AutG}  (st ühesuguseid sümmeetriaomadusi), kuid nende struktuursed mudelid  S  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  S  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