Graafi struktuur

Graafi struktuur on graafi tippude ja tipupaaride omadus olla invariantselt seostatud, st organiseeritud mingil kindlal viisil. Graafi struktuur on isomorfsete graafide klassi täielik invariant.

Selgitusi[muuda | muuda lähteteksti]

Mõiste struktuur ümber valitseb segadus. Ühest küljest on see muutunud mingiks iga asja kohta käivaks ähmaseks omadussõnaks. Teisest küljest on see koosluse kindel karakteristik, küllaltki rangelt määratletud kategooria, st struktuur kui niisugune ^[1]^[2]. Kolmandaks, on neid kes peavad õigeks rääkida vaid konkreetse objekti struktuurist, näiteks asutuse struktuur, kivimi struktuur, bioloogiline struktuur jne. Esimesed ja kolmandad ei tunnista struktuuri kui niisuguse defineerimist.

Graafi struktuurist räägitakse ka kui selle mingitest spetsiifilistest omadustest. Näiteks, graafi algebralise struktuuri all mõeldakse selle teatud algebralisi omadusi.

Rangelt võttes nimetatakse struktuuriks süsteemi abstraktsiooni, selle "skeletti", kus elemendid ja nendevahelised seosed on minetanud oma empiirilised tähendused ja vaatluse all on peamiselt nende organiseeritus ja sümmeetria omadused ("positsioonid"). Struktuur ise ongi kujutatav graafina ning seotud invariantsuse ja isomorfismiga. Graaf ise on paljuaspektiline objekt. Struktuuri kui niisugust uurib struktuurisemiootika.

Struktuuri, süsteemi, invariandi ja sümmeetriaklassi ehk positsiooni mõisted on lihtsalt ja piltlikult selgitatavad Rubiku kuubiku põhjal.

Kommentaarid Rubiku kuubiku kohta:

a) Rubiku kuubiku igal tahul on üks element keskel, neli elementi servades ja neli elementi nurkades, kokku 9x6=54 elementi.
b) Seega moodustavad kuubiku 6 elementi keskpositsiooni, 24 elementi nurkpositsiooni ja 24 elementi servpositsiooni.
c) Kihti pöörates muutub süsteem, sest suhted empiiriliste omaduste (värvide) vahel muutuvad. Elementide "positsioonid" ei muutu, need jäävad invariantseks.
d) Rubiku kuubik on esitatav struktuuri säilitava graafina millel on kolm tipupositsiooni.
e) Elementide "positsioonid" langevad kokku rühma AutG orbiitidega.

Nii on ka struktuuri üldine tähendus kujutatav graafidel.

Graafi struktuuri tuvastamine[muuda | muuda lähteteksti]

Graafi esitamiseks on kasutatud mitmesuguseid lokaalseid (tippe puudutavaid) ja globaalseid (graafitervikut puudutavaid) invariante. Niisugust lähenemist nimetatakse graafi kanooniliseks esitamiseks (inglise: graph canonization) ^[3]. Paraku ei sisalda seni teada olevad kanoonilised esitused teavet graafi struktuuri kohta. Graafi esitamisel tema automorfismide rühma põhjal tekib keerukama struktuuri puhul palju küsitavusi.

Graafi $G$ struktuur $S$ on identifitseeritav atribuut, $\,S={\mathfrak {F}}(G)$ . Identifikaatoriteks on tipupaaride ${i,j}$ ümbruste ühisosi $N_{i}\cap N_{j}$ kujutavate binaargraafide $g_{i,j}$ invariandid ^[4].

Vastav algoritm ${\mathfrak {F}}$ tuvastab: a) iga mittenaabertippude paari jaoks nendevahelise kauguse $-d$ ; b) iga naabertippude paari jaoks selle kuuluvuse vöösse suurusega $+d$ ; c) mõlemal juhul ka vastavat binaargraafi moodustavate tippude arv $n$ ja servade arv $m$ .

Saadud invariandinelikute $\pm {d.n.m.}_{i,j}$ ehk binaarmärkide korrastatud (dekomponeeritud) süsteem kujutab endast graafi struktuuri esitavat (kirjeldavat) semiootilist mudelit $GS$ .

Graafi struktuuri uurimine tähendab selle mudeli $GS$ uurimist. Erinevate struktuuride arv võrdub mitteisomorfsete graafide arvuga. Struktuuride ekvivalentsuse tuvastamine kujutab endast vastavate mudelite ekvivalentsuse lihtsat fikseerimist.

Structural equivalence — Näide 2. Graafid G ja H ning nende struktuuride esitus semiootiliste mudelite abil

Kommentaarid semiootiliste mudelite kohta:

a) Erinevad graafid $G$ ja $H$ omavad ühesuguseid ehk ekvivalentseid semiootilisi mudeleid, st et nende struktuurid on ekvivalentsed ja vastavad graafid on isomorfsed $G\simeq H$ .
b) Semiootiline mudel on tuvastanud struktuuri sümmeetriaomadused kolme tipuorbiidi ("positsiooni") ja viie tipupaari orbiidi, sh kahe "mitteserva orbiidi" näol.
c) Vastavused struktuuride vahel avalduvad tipupaariorbiitide substitutsioonide tasemel.
d) Binaarmärgid tuvastavad iga tipupaari puhul selle sidususe, kuuluvuse teatud suurusega teesse, vöösse või klikki, näiteks D: +2.5.7 tähendab: see tipupaar kuulub rohkem kui ühte vösse pikkusega d=2+1.
e) Üldjuhul on struktuur tuvastatav nendesamade binaarmärkide tasemel kuid teatud sümmeetriliste graafide puhul peab kasutama täpsustatud binaarmärke.

Tegemist on graafide identifitseerimisega. Binaarmärke on kasulik täpsustada seosmaatriksit $E$ korrutades (astendades) seda teatud astmeni $E^{n}$ . Seda tehes suurenevad nii selle elementide väärtused kui ka erinevate väärtuste arv. Suurenemine toimub vaid teatud astmeni $n$ , pärast seda see lakkab. Need väärtused kujutavad endast binaarmärke, mis tuvastavad tipupaari positsioone, st binaarpositsioone. Nimetagem neid binaarmärke produktiivseteks binaarmärkideks.

Põhimõte, et graafi struktuuri tuvastamine toimub tipupaaride süvaidentifitseerimise printsiibil saadava täieliku invariandi näol jääb kehtima ^[5].

Graafi struktuuri omadusi[muuda | muuda lähteteksti]

Semiootiline mudel $GS$ esitab selle klassi graafide ühist struktuuri. Graafide isomorfismi tuvastamine ei tähenda veel struktuuri tuvastamist, see kujutab endast vaid nende ekvivalentsuse kindlaksmääramist.

Struktuuri olulisemaid omadusi on sümmeetria. Sümmeetria on graafi tippude ja tipupaaride omadus jaotuda orbiitideks, st ekvivalentsusklassideks ehk positsioonideks. Sümmeetriaomadused, st orbiidid (positsioonid) on semiootilises mudelis äratuntavad kui binaarmärkide ekvivalentsusklassid. Äratuntavad on nii tipu- kui ka tipupaari orbiidid (positsioonid), sh viimase puhul serva- ja "mitteserva"' orbiidid. See lihtne moodus asendab ja katab nende tavapärast käsitlemist automorfismirühmade AutG abil ^[6]^[7].

Orbiitidel on oluline rolli graafi struktuuri uurimisel. On fikseeritud seaduspärasusi sümmeetriaomaduste ja tugevregulaarsuse vahel ^[8]. Sümmeetriatunnuste (graafi orbiitide arvu ja nende võimsuste) baasil on välja töötatud sümmeetriaomaduste klassifikatsioon. Esitatakse moodus sümmeetria mõõtmiseks. Ka asümmeetria on sümmeetriaomadus.

Igale tipupaari orbiidile (positsioonile) vastab üks positsioonistruktuur. Selle moodustavad orbiiti kuuluvad tipupaarid ning see kujutab endast vahendit struktuuri nö varjatud külgede uurimiseks. Näiteks, on selgunud, et Folkmani graafi üheks positsioonistruktuuriks on Peterseni graaf, jne. Varjatud külgi on veel teisigi.

Vaata ka[muuda | muuda lähteteksti]

Viited[muuda | muuda lähteteksti]

↑ Schmidt, Henrik, 1991. Philosophisches Wörterbuch. Stuttgart. ISBN 5250017940
↑ Новая философская энциклопедия. 2001, Москва. ISBN 9785244011159
↑ Gurevich, Y. From Invariants to Canonization. – The Bull. of Euro. Assoc. for Comp. Sci., No. 63, 1997
↑ Tevet, John-Tagore. 2002. Semiotic testing of the graphs. S.E.R.R., Tallinn.
↑ J.-T. Tevet. Graafide identifitseerimine. S.E.R.R., Tallinn, 2017 ISBN 9789949816514
↑ Tevet, John-Tagore. 2010. Graafide varjatud külgi. S.E.R.R,. Tallinn, ISBN 9789949213108
↑ Tevet, John-Tagore. 2013 Nature of the Structure. S.E.R.R., Tallinn, ISBN 9789949334650
↑ Tevet, John-Tagore, 2007. Bisümmeetrilise struktuuri semiootika. S.E.R.R,. Tallinn

Välislingid[muuda | muuda lähteteksti]

Selgitusi graafi struktuuri kohta (PDF)
Struktuuri identifitseerimine (PDF)

[AQjL7-1] Schmidt, Henrik, 1991. Philosophisches Wörterbuch. Stuttgart. ISBN 5250017940

[L46iF-2] Новая философская энциклопедия. 2001, Москва. ISBN 9785244011159

[OKZMv-3] Gurevich, Y. From Invariants to Canonization. – The Bull. of Euro. Assoc. for Comp. Sci., No. 63, 1997

[vQBdF-4] Tevet, John-Tagore. 2002. Semiotic testing of the graphs. S.E.R.R., Tallinn.

[C2fYi-5] J.-T. Tevet. Graafide identifitseerimine. S.E.R.R., Tallinn, 2017 ISBN 9789949816514

[KrMnz-6] Tevet, John-Tagore. 2010. Graafide varjatud külgi. S.E.R.R,. Tallinn, ISBN 9789949213108

[5afdF-7] Tevet, John-Tagore. 2013 Nature of the Structure. S.E.R.R., Tallinn, ISBN 9789949334650

[V8bbj-8] Tevet, John-Tagore, 2007. Bisümmeetrilise struktuuri semiootika. S.E.R.R,. Tallinn

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]