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[muuda | muuda lähteteksti]

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 ^[1]. 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 ^[2].

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 ^[3]. 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[muuda | muuda lähteteksti]

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 ^[4]^[5].

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[muuda | muuda lähteteksti]

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 ^[6].

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

Vaata ka[muuda | muuda lähteteksti]

Viited[muuda | muuda lähteteksti]

↑ D. W. Farmer. Groups and Symmetry. Providences. RI: Amer. Math. Soc. 1995
↑ R. Frucht. Herstellung der Graphen mit vorgegebener Gruppe. Compositio Math. 8 (1938) 239-250
↑ В. А. Емеличев и др. Лекции по Теории Графов. Наука, 1990
↑ J.-T. Tevet. Semiotic Testing of the Graphs. S.E.R.R. Tallinn, 2001
↑ J.-T. Tevet. Graafide varjatud külgi. S.E.R.R., Tallinn, 2010 ISBN 9789949213108
↑ J.-T. Tevet. What is a graph and how to study it. S.E.R.R., Tallinn, 2017. ISBN 9879949817559.

[1] D. W. Farmer. Groups and Symmetry. Providences. RI: Amer. Math. Soc. 1995

[2] R. Frucht. Herstellung der Graphen mit vorgegebener Gruppe. Compositio Math. 8 (1938) 239-250

[3] В. А. Емеличев и др. Лекции по Теории Графов. Наука, 1990

[4] J.-T. Tevet. Semiotic Testing of the Graphs. S.E.R.R. Tallinn, 2001

[5] J.-T. Tevet. Graafide varjatud külgi. S.E.R.R., Tallinn, 2010 ISBN 9789949213108

[6] J.-T. Tevet. What is a graph and how to study it. S.E.R.R., Tallinn, 2017. ISBN 9879949817559.

[1]

[2]

[3]

[4]

[5]

[6]