Graafi paljuaspektilisus: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
täpsustamine pooleli |
täiendatud |
||
6. rida:
Mõned graafide [[struktuurisemiootika|struktuurisemiootilise]] käsitlemise käigus ilmsiks tulnud atribuudid:
===[[Graaf]] ja selle [[graafi struktuur|struktuur]]===
Nii [[süsteem]], [[graafi struktuur|struktuur]] kui ka [[graaf]] on moodustised mis koosnevad ''elementidest'' (osistest) ja nendevahelistest ''seostest'' (suhetest). Süsteemi puhul mängivad olulist rolli selle elementide ja seoste [[empiililine|empiirilised]] omadused ja [[Funktsioon (matemaatika)|funktsioon]]id. Struktuur, kui süsteemi [[abstraktsioon]] kajastab vaid elementide omavahelist organiseeritust, elementide empiirilised omadused ei puuduta struktuuri kui niisugust. Nii süsteem kui ka struktuur on kujutatav graafina – graaf on struktuuri eksplikaat. [[Graafi struktuur]] kujutab endast püsivat organiseeritust, mis on fikseeritud kui elementide kuuluvus teedesse, [[graafi klikk ja vöö|vöödesse, klikkidesse]] ja ekvivalentsusklassidesse ehk „positsioonidesse“ struktuuris. [[Graafi struktuur]] on kujutatav ''semiootilise mudeli'' näol mis on [[isomorfism|isomorfsete]] graafide täielik [[graafi invariant|invariant]].
===[[Graafi orbiit]] ja „positsioon“ [[graafi struktuur]]is===
Orbiit (väga ebakohane termin!) on [[rühmateooria]] atribuut, mis sisuliselt kujutab endast rühma elementide ekvivalentsusklassi. On uuritud graafi [[automorfism|automorfismide rühma]] ''AutG'' ning [[permutatsioon|permutatsioonitehnika]] võtetega tuvastatud graafi tippude (haruharva ka servade) orbiite. Needsamad [[graafi orbiit|orbiidid]] on tuvastatavad ka graafi ''tipupaaride süvaidentifitseerimise teel''. Struktuursest aspektist on orbiiti sobivam nimetada ''ekvivalentsusklassiks'' või ''positsiooniks struktuuris''.
15. rida:
[[Graafi kanooniline esitus]] on graafi esitus mingil kaudseid invariante kasutaval viisil <ref> Y. Gurevich (1997). ''From Invariants to Canonization''. – The Bull. of Euro. Assoc. for Comp. Sci., No. 63, 1997 </ref>. Paraku ei sisalda niisugused esitused teavet [[graafi struktuur]]i ega [[graafi sümmeetria|sümmeetriaomaduste]] kohta. Semiootiline mudel, kuigi seda võib ka kanooniliseks esitiseks tituleerida, on struktuuri „tekst“ mis esitab seda [[isomorfism]]i ja [[graafi sümmeetria|sümmeetriaomaduste]] („positsioonide“) täpsusega. Graafide puhul on tekkinud [[sümmeetria]] mõiste ümber segadusi. On neid kes nimetavad sümmeetriliseks lihtgraafi ja ebasümmeetriliseks suunatud graafi. Suunatud graafi ühes suunas kulgevat teed nimetatakse transitiivseks. On neidki kes seostavad graafi sümmeetriat orbiitide ehk ekvivalentsusklassidega. Ühe tipuorbiidiga graafi nimetatakse ''transitiivseks'' orbiiti moodustavate automorfismide transitiivsuspiirkonna mõttes. Mõned nimetavad sellist graafi ''tippudest sümmeetriliseks'' ja ühe servaorbiidiga graafi ''servadest sümmeetriliseks''. See on korrektne, kuid sellega ka piirdutakse. [[Graafi orbiit]]ide (ekvivalentsusklasside) tundmine võimaldab [[graafi sümmeetria]] omadusi täpsustada ning fikseerida huvitavaid atribuute agu [[orbiitgraaf|positsioonistruktuurid]] jt. Graafi uurides ei huvituta tavaliselt selle [[graafi täiend]]ist. Miks? Struktuuri uurimisel on selle täiendi esiletoomine endastmõistetav. Struktuuri ja selle täiend sisaldavad ühesuguseid [[graafi orbiit|positsioone]] (orbiite) kuigi tipupaaride puhul erinevate märkidega, neil on ühesuguseid sümmeetria ja [[tõenäosus]]likke parameetreid. Nii mõnigi struktuurne omadus on väljaloetav tema täiendi kaudu. Struktuuri uurimine tähendab [[graafi struktuur|semiootilise mudeli]] uurimist.
===Graafide [[isomorfism]] ja graafi struktuuride ekvivalentsus===
Graafide [[isomorfism]]i määratletakse tavaliselt kui ''bijektsiooni, mis säilitab tippude naabrused''. H. Whitney täpsustab: ''bijektsioon, mis säilitab naabrused pluss veel midagi'' <ref> H. Whitney (1932) ''2-isomorphism graphs''. August 30 A.M.S. </ref>. [[Ülo Kaasik]] väidab: ''bijektsioon, mis säilitab struktuuri'' <ref>Ü. Kaasik (2003). ''Matemaatikaleksikon''. Tartu, ISBN 9985941772 </ref>. Kuigi ta pole struktuuri defineerinud ja graafide isomorfismi puhul graafi struktuuriga kokku ei puututa, on see täiesti täpne. Struktuuride ekvivalentsus on ''bijektsioon tipupaari [[graafi orbiit|positsioonide]] (binaarorbiitide) tasemel''. Seda on [[graafi struktuur|semiootiliste mudelite]] baasil lihtne tuvastada. Ekvivalentsete struktuuridega graafid on [[isomorfism|isomorfsed]]. Kunagi on keegi (ilmselt mingi kindla algoritmi põhjal) kindlaks teinud, et graafide isomorfismi tuvastamise [[keerukus|ajaline keerukus]] on ''NP''. See tõdemus on muutunud paljudele dogmaks, millest kramplikult kinni hoitakse. Semiootiliste mudelitega opereerimisel selleni ei küüni.
25. rida:
==Vaata ka==
*[[Graafide identifitseerimine]]
*[[Graafi struktuur]]
*[[Graafi sümmeetria]]
| |||