|
'''Struktuurisemiootika''' ([[inglise keel]]es ''semiotics of the structure'') on on [[Eesti]] ja [[India]] uurimisrühmade poolt viljeletav uurimissuund [[graafiteooria]] ja [[semiootika]] piirimail <ref> John-Tagore Tevet. 1990. ''Interpretation on some Graph Theoretical Problems''.
{{toimeta}}
Estonian Academy of Sciences.</ref>. Uuritakse peamiselt [[graafi struktuur]]i ja [[graafide süsteem]]iga seotud nö „varjatud külgi“ <ref> John-Tagore Tevet. 2010. ''Graafide varjatud külgi''. S.E.R.R, Tallinn, ISBN 9789949213108.</ref>. [[Semiootika]] roll seisneb siin [[struktuur]]sete [[invariant]]ide [[interpretatsioon|interpreteerimises]].
'''Struktuurisemiootika''' ([[inglise keel]]es ''semiotics of the structure'') on uurimissuund [[graafiteooria]] ja [[semiootika]] piirimail. See kujutab endast praktilist moodust [[struktuur]]i ja selle omaduste semiootiliseks modelleerimiseks ([[inglise keel]]es ka ''computational semiotic'') <ref> Rieger, Burghard B. 1998. A Systems Theoretical View on Computational Semiotics. Modeling text understanding as meaning constitution by SCIPS, in: ''Proceedings of the Joint IEEE Conference on the Science and Technology of Intelligent Systems (ISIC/CIRA/ISAS-98)'', Piscataway, NJ (IEEE/Omnipress) 1998, pp. 840-845 </ref>.
GraafeStruktuurisemiootika on mitmesuguste kaudseteseotud [[graafi invariant]]ide ([[polünoom]]ide, [[spekter|spektrite]] jt) baasil esitatud nö [[graafi kanooniline esitus|kanooniliselkanoonilise kujulesituse]], [[isomorfism]]i<ref> Y.Ashay Gurevich.Dharwadker ''Fromand InvariantsJohn-Tagore toTevet. Canonization''. – The Bull.Graph ofIsomorphism EuroAlgorithm''. AssocProc. forInstitute Comp.of Sci.Mathematics, No.Amazon 63Books, 1997ISBN 1466394377 </ref>. Paraku ei sisalda niisugused esitused teavet, [[graafi struktuurtäiend|täiendi]]i, ja[[regulaarne sellegraaf|regulaarsuste]], [[graafi sümmeetria|sümmeetriaomaduste]], kohta.[[graafi Graafiorbiit|orbiitide]], esitamisel[[Ulami temahüpotees|taastatavuse]], [[rühmjuhuslik (matemaatika)graaf|automorfismide rühmajuhuslikkuse]] põhjal tekib keerukama struktuuri puhul paljujt küsitavusiprobleemidega.
On koostatud teavik uurimisrühmade tööst <ref> John-Tagore Tevet. 2012. ''The story of S.E.R.R.''. S.E.R.R. Tallinn, ISBN 9789949308774 </ref>.
== Selgitus ==
[[Pilt:Rubik's cube.svg|thumb|Näide 1. Rubiku kuubik kui struktuuri säilitav süsteem.]]
Struktuuri all mõistetakse siin selle üldist, abstraktset tähendust kui elementidevahelist seostust või organiseerimisvormi <ref>Schmidt, Henrik, 1991. Philosophisches Wörterbuch. Stuttgard. ISBN 5250017940</ref> <ref>Новая философская энциклопедия. 2001, Москва. ISBN 9785244011159</ref>. ''[[Graafi struktuur]]'' on selle tippude ja tipupaaride omadus olla graafis invariantselt seostatud, organiseeritud mingil kindlal viisil. Nii on ka struktuuri üldine tähendus kujutatav graafidel. Graafi struktuur on [[isomorfism|isomorfsete]] graafide klassi täielik [[invariant]].
''[[Struktuur]]i'' ja ''[[invariant|invariandi]]'' mõisted on lihtsalt ja piltlikult selgitatavad [[Rubiku kuubik]]u põhjal.
Kommentaarid Rubiku kuubiku elementide kohta:
a) Rubiku kuubiku igal tahul on üks element ''keskel'', neli elementi ''servades'' ja neli elementi ''nurkades''.
b) Kihti pöörates elementide "positsioonid" ei muutu, need jäävad ''invariantseks''.
c) Seega moodustavad kuubiku 6 elementi '''''„keskpositsiooni“''''', 24 elementi '''''„nurkpositsiooni“''''' ja 24 elementi '''''„servpositsiooni“'''''.
d) Rubiku kuubik on esitatav struktuuri säilitava graafina millel on '''''kolm tipupositsiooni'''''.
e) Elementide "positsioonid" langevad kokku [[rühm (matemaatika)|rühma AutG]] '''''[[graafi orbiit|orbiitidega]]'''''.
== Lähteprintsiip ==
Lähtugem hüpoteetilisest kuid töötavast põhimõttest, et graafi ''G'' struktuur ''S'' on identifitseeritav (mõõdetav) atribuut, <math>\,S=\mathfrak{F}(G)</math>, ning on modelleeritav tema „elementaarosakeste“, st tipupaaride identifitseerimise ehk märgistamise teel <ref> John-Tagore Tevet, 1990. ''Interpretations on some Graph Theoretical Problems'', Estonian Acad. of Sciences. </ref>.
==Teostus==
Vastav [[algoritm]] <ref> Tevet, John-Tagore. 2002. Isomorphism and Reconstruction of the Graphs: A constructive approach and development. ''S.E.R.R. '' Tallinn. </ref> rajaneb lokaalsetel [[graafi invariant|invariantidel]] ehk märkidel. See tuvastab: a) iga ''naabertippude paari'' jaoks selle kuuluvuse ''vöösse'' (vööde parve või ''oksa'') ning selle suuruse '''''+d'''''; b) iga ''mitte-naabertippude paari'' jaoks nendevahelise kauguse '''''–d''''' ja vastava ''ahela'' (või ahelate parve; c) mõlemal juhul ka vastavat vööd või ahelat moodustavate tippude arv '''''n''''' ja servade arv '''''m'''''.
Saadud invariant-nelikute, '''''paari- ehk binaarmärkide d.n.m.''''' korrastatud (dekomponeeritud) süsteem on '''''semiootiline mudel S''''', kui struktuuri kirjeldus.
Struktuuri uurimine tähendab selle mudeli '''''S''''' uurimist. Erinevate struktuuride arv võrdub mitteisomorfsete graafide arvuga. Struktuuride ekvivalentsuse tuvastamine kujutab endast vastavate mudelite ekvivalentsuse lihtsat fikseerimist. [[File:Equivalence.jpg|thumb|alt=Structural equivalence|Näide 2. Struktuuride ekvivalentsus ja graafide isomorfsus.]]
Kommentaarid näitele 2: a) Erinevad graafid omavad siin ''ekvivalentseid semiootilisi mudeleid'', st et nende ''struktuurid on ekvivalentsed'' ja vastavad ''graafid on isomorfsed''. b) Semiootiline mudel on tuvastanud kolm tipupositsiooni (-orbiiti) ja viis tipupaari [[graafi orbiit|orbiiti]], sh kaks „mitteserva orbiiti“ c) Vastavused struktuuride vahel avalduvad tipupaari-orbiitide tasemel. d) Binaarmärgid tuvastavad iga tipupaari puhul tema "seisundi" struktuuris, näiteks '''''E: +3.6.10''''' tähendab: "see tipupaar kuulub rohkem kui ühte vösse pikkusega ''d=4''". e) Üldjuhul on struktuur tuvastatav oma ''lähte binaarmärkide'' tasemel kuid teatud sümmeetriliste graafide puhul peab kasutama ''täpsustatud binaarmärke''.
''Struktuurne ekvivalentsus'' on [[isomorfism]] tipupaari [[graafi orbiit|orbiitide]] tasemel. See on tuvastav vastavate mudelite lihtsa võrdlemise teel. Erinevate struktuuride arv võrdub graafide erinevate [[isomorfismiklass]]ide arvuga. Semiootiline mudel '''''S''''' esitab selle klassi graafide ühist struktuuri. Graafide isomorfismi tuvastamine ei tähenda veel struktuuri tuvastamist, see kujutab endast vaid nende [[ekvivalentsus]]e kindlaksmääramist.
Struktuuri olulisemaid omadusi on [[graafi sümmeetria|sümmeetria]]. '''''Sümmeetria''''' on graafi tippude ja tipupaaride omadus jaotuda ''[[graafi orbiit|orbiitideks]]'', st ''ekvivalentsus- või transitiivsusklassideks''. 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 [[rühm (matemaatika)|automorfismirühmade]] '''''AutG''''' abil <ref>Tevet, John-Tagore, 2010. Graafide varjatud külgi. ''S.E.R.R'',. Tallinn, ISBN 9789949213108</ref>.
[[graafi orbiit|Orbiitidel on oluline rolli graafi struktuuri uurimisel. On fikseeritud seaduspärasusi ''[[graafi sümmeetria|sümmeetriaomaduste]]'' ja ''[[regulaarne graaf|tugevregulaarsuse]]'' vahel <ref>Tevet, John-Tagore, 2007. Bisümmeetrilise struktuuri semiootika. ''S.E.R.R'',. Tallinn</ref>. Sümmeetriatunnuste (graafi orbiitide arvu ja nende võimsuste) baasil on välja töötatud ''[[graafi sümmeetria|sümmeetriaomaduste]] klassifikatsioon''. Esitatakse moodus sümmeetria [[mõõt]]miseks. Ka asümmeetria on sümmeetriaomadus.
Igale tipupaari orbiidile (positsioonile) vastab üks '''''[[orbiitgraaf|positsioonistruktuur]]'''''. Selle moodustavad orbiiti kuuluvad tipupaarid ning see kujutab endast vahendit struktuuri nö varjatud külgede uurimiseks. Näiteks, on selgunud, et [[Folkmani graaf]]i üheks [[orbiitgraaf|positsioonistruktuuriks]] on [[Peterseni graaf]], jne.
== Arendus ==
Igale tipupaari [[graafi orbiit|orbiidile]] (positsioonile) vastab ka üks '''''naaberstruktuur''''', mis saadakse serva eemaldamisel või lisamisel orbiiti kuuluva tipupaari vahele. Need moodustavad ''n-'' tipuliste ''[[graafide süsteem|struktuuride konstruktiivse süsteemi]]'' <ref>Tevet, John-Tagore, 2007. System analysis of the graphs. Tallinn, online: (http://tallinn.ester.ee/record=b2297694~S1*est )</ref>. See on seotud [[Ulami hüpotees]]i ehk '''''rekonstruktsiooniprobleemiga'''''.
Rekonstrueerimisprobleemi puhul võib rääkida suurimatest alamgraafidest nii tippude G/v kui ka servade G/e eemaldamise mõttes <ref> Harary, Frank. 1964. On the reconstruction of a graph from a collection of subgraphs. – Theory of Graphs and its Applications - ''Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52'' </ref>. Servade puhul saab rääkida ka väikseimatest ülemgraafidest.
[[File:Tevetlattice.jpg|thumb|Näide 3: Kuueelemendiliste struktuuride konstruktiivse süsteemi võre esimene pool.]]
Vanameistri W. T. Tutte järgi peaks rekonstruktsiooniprobleemi lahenduse otsingud baseeruma ''isomorfismiklassidel'', mis loob täiesti uue pildi sellest probleemist. <ref> Tutte. W. T. 1998. Graph Theory As I Have Known It. ''Clarendon Press, Oxford.'' </ref>
Isomorfismiklass kujutab endast isomorfsete graafide hulka. Isomorfsed graafid omavad üht ja sama [[struktuur]]i. See struktuur on kujutatav kanooniliselt vastava semiootilise mudeli '''''S''''' näol. Igal graafil (struktuuril) on oma suurimad alamgraafid (naaberstruktuurid) ja väikseimad ülemgraafid (naaberstruktuurid) mis saadakse vastavalt serva (seose) eemaldamisel või lisamisel. Kõik n-tipulised graafid (n-elemendilised struktuurid) moodustavad [[võre]] mille elementideks („tippudeks“) on struktuurid (vastavat isomorfismiklassi esindavad graafid) ja seosteks („servadeks“) struktuuridevahelised seosed.
Kommentaarid näitele: a) Iga graaf selles kuueelemendilise struktuuride võres esindab oma isomorfismiklassi ehk struktuuri, mis on esitet maatriksi '''''S''''' näol. b) Iga struktuur selles võres on mõne(de) teise (teiste) struktuuri(de) suurim alamstruktuur või väikseim ülemstruktuur. c) Iga struktuur on '''''dekomponeeritav''''' oma suurimateks alamstruktuurideks või '''''komponeeritav''''' oma väikseimateks ülemstruktuurideks. d) Iga struktuur on '''''rekonstrueeritav (taastatav)''''' oma nii oma suurimate alamstruktuuride kui ka väikseimate ülemstruktuuride baasil. e) Eelmises näites esitatud struktuur kannab siin järjekorranumbrit 22. f) Esitatud struktuuride täiendid asuvad sümmeetriliselt selle võre teises pooles. g) Kuueelemendiliste struktuuride (mitteisomorfsete graafide) arv on 156.
Kõik struktuurid (graafid) kuuluvad niisugustesse võredesse. ''Naaberstruktuurideks'' on siin nii suurimaid alam- kui ka väiksemaid ülemstruktuure. Rekonstruktsiooniprobleem seisneb vaid küsimuses: Kas erinevad struktuurid saavad omada täpselt ühesuguseid naaberstruktuure. Sellele probleemile üksikute graafiklasside pidi lähenemine ei ole mõttekas.
==Kokkuvõte==
Semiootiline modelleerimine on täiesti uus lähenemine graafidele. See rajaneb tipupaaride identifitseerimise (mõõtmise) teel saadud täpsel mudelil, mis sisaldab mitmesugust teavet graafi struktuuri ja selle sümmeetriaomaduste kohta. Semiootiline mudel on vahend graafi struktuuri uurimiseks - ''struktuur on isomorfsete graafide täielik invariant''. Graafi struktuur kaudu on võimalik selgitada ka struktuuri üldist mõistet.
Teisest küljest on tegemist ka mõneti delikaatse teemaga. "Struktuur" on hargnenud kas eritähenduslikeks mõisteteks või muutunud ähmaseks omadussõnaks ning tänapäeval puudub selle mõiste kõiki rahuldav määratlus, teiseks, mõned matemaatikud ei aktsepteeri graafide struktuurisemiootilist käsitlemist ja kolmandaks, semiootikud ei tunne mingit huvi struktuurisemiootika vastu. Vaatamata sellele avab struktuurisemiootika graafide „varjatud külgi“, lahendab mõningaid klassikalisi probleeme mitteklassikalisel viisil ning püstitab ja lahendab uusi.
Struktuuri ja struktuurse ekvivalentsuse tuvastamise keerukus sõltub vaid elementide (tippude) arvust ja see ei ole võrreldav isomorfismi tuvastamise atrubuutidega.
==Viited==
| 