Vikipeedia

Graafide identifitseerimine: erinevus redaktsioonide vahel

Sirvi ajalugu interaktiivselt
← Vanem muudatusUuem muudatus →
Eemaldatud sisu Lisatud sisu
VisuaalneVikitekst
Kanejuku (arutelu | kaastöö)
247 muudatust
täiendav teave
Kanejuku (arutelu | kaastöö)
247 muudatust
kirjavigade parandus
5. rida:
[[File:Gidenting.jpg|pisi|Identification of graphs by exponantation the adjacency matrix]]
 
[[Graaf]]i <math>G</math> põhiline omadus on tema '''[[graafi struktuur|struktuur]]''', organiseeritus, mis rajaneb elementidevahelistele suhetele. Struktuur ise on kujutatav graafina <math>G</math> kusjuures ''[[isomorfism|isomorfsed]] graafid omavad ühesugust struktuuri''. Struktuuri põhilisteks karakteristikuteks on tema '''[[graafi sümmeetria|sümmeetriaomadused]]''', mis avalduvad sarnaste elementide (st tippude ja tipupaaride) näol, mida [[rühmateooria]] aspektist '''[[graafi orbiit]]ideks''' (või transitiivsuspiirkondadeks, ekvivalentsusklassideks) nimetatakse.
 
Graafi elementaarosised on tipupaarid (mitte tipud ise) ja selle elementaarsed sümmeetriaosised on tipupaariorbiidid <math>\Omega_{n}</math>. Tipupaare (st tipupaaride vahelisi suhteid) on püütud identifitseerida nende ''ümbruste ühisosa iseloomustavate [[graafi invariant|invariantide]] abil''.
 
Efektiivsemaks on osutunud ''[[graafi seosmaatriks]]i astendamine (korrutamine iseendaga)''. Kui algses seosmaatriksis <math>E^1</math> on vaid kaks tipupaaride ekvivalentsusklassi: servedservad ja mitteservad, siis algse maatriksi korrutamisel iseendaga <math>E^1\cdot E^1=E^2</math> suureneb klasside arv <math>p</math>, mis toimub teatud astmeni <math>E^n</math>, <math>E^{n-1}\cdot E^1= E^n</math> ja siis seiskub. <ref>[[John-Tagore Tevet|J.-T. Tevet]]. ''Graafide varjatud külgi''. S.E.R.R., Tallinn, 2010 ISBN 9789949213108 </ref>.<ref> J.-T. Tevet. ''Semiotic Modelling of the Structure''. ISBN 9781503367456, 2014, Amazon Books</ref> <ref> J.-T. Tevet. ''Graafide identifitseerimine''. ISBN 9789949816514, 2017, S.E.R.R., Tallinn </ref>.
 
Seega, iga astme <math>n</math> korral suureneb reeglina tipupaare iseloomustavate astmeelementide <math>e^n_{ij}</math> erinevate väärtuste arv <math>p</math>. Moodustada nende erinevate väärtuste jada <math>S^n_p=e^n_{1}< e^n_{2}< </math> … <math> < e^n_{p}</math> .
Kui astme <math>n+1</math> korral erinevate väärtuste arv <math>p</math> enam ei suurene, siis peatada korrutamine ja moodustada väärtuste jada <math>S^n_p</math> baasil igale reale <math>i</math> vastav väärtuste sagedusvektor <math>u_i</math>.
Järjestada (transponeerida) saadud maatriksastme <math>E^n</math> read <math>i</math> ja veerud <math>j</math> leksikograafiliselt vastavalt nende sagedusvektoritele <math>u_i</math>. Saame korrastatud maatriksastme <math>E^n_{ord}</math>.
Salvestada maatriksaste <math>E^n</math> ja selle korrastatud maatriksaste <math>E^n_{ord}</math>.
 
Nii [[struktuurimudel]] <math>SM</math> kui ka maatriksaste <math>E^nn_org</math> on võrdväärsed, teineteist täiendavad graafide identifitseerimise atribuudid. Kuigi <math>SM</math> eristab ja esitab tippudevahelisi suhteid küllaltki täpselt, võivad need osutuda vahest mittetäielikeks invariantideks. <math> E^n</math> elemendid on küll täielikud invariandid, kuid ei erista omavahel graafi servi ega nende puudumist.
 
== Orbiitide (positsiooniklasside) põhiomadused ==
26. rida:
3. Kui graafi <math>G</math> ''mitteservad'' <math>ne_{1}, ne_{2}</math> <math>\ldots</math> <math>\ldots</math> kuuluvad samasse positsiooni (orbiiti) <math>\Omega_{n}</math> ''siis on ülemgraafid'' <math>G\cup e_{1}</math> <math>\simeq</math> <math>G\cup e_{2}</math> <math>\simeq</math> <math>\ldots</math> ''isomorfsed''.
 
4. Tipupaari-orbiitide <math>\Omega_{n}</math> baasil saadud isomorfsed alamgraafid kujutavad endast graafi <math>G</math> ''naaber alamstruktuuri'' ja/või ''naaber ülemstruktuuri'', mida üldistatult lihtsalt ''''naaberstruktuuriks'''' <math>G^{adj}</math> nimetame.
 
5. Iga naaberstruktuur <math>G^{adj}</math> omab nö “reversiivsetreversiivset orbiiti”orbiiti <math>\Omega^rev_{n}</math> millele rakendatud servaoperatsioon “taastab''taastab lähtestruktuuri“lähtestruktuuri'' <math>G</math>. Seda struktuuridevahelist seost nimetame ''''mofisdmiks''''
 
6. Kõikide ''n'' tipuliste naaberstruktuuride ''jadade parv'' tühistruktuuri ja täisstruktuuri vahel moodustab ''n-tipuliste [[graafide süsteem]]i''. Selle süsteemi graafe võime omakorda kujutada tippudena ja nendevahelisi naabrusi ehk morfisme servadena.
 
Näiteks: neljatipuliste [[graafide süsteem]] kujutab endast 11 elemendilist võre millel on 14 serva; viietipuliste süsteem koosneb 34 struktuurist ja 72 seosestmorfismist nende vahel; kuuetipuliste süsteem koosneb 156 struktuurist ja 572 seoaestmorfismist nende vahel, jne. Kõik see on seotud ülemineku tõenäosusteüleminekutõenäosuste ja ka [[Ulami hüpotees]]iga serva-eralduste aspektist.
 
Graaf mis koosneb orbiiti <math>\Omega_{n}</math> kuuluvatest servadest nimetatakse ''[[orbiitgraaf]]iks'' <math>G_{n}</math>.
38. rida:
== Orbiitgraafide omadusi ==
 
1. [[Orbiitgraaf]] <math>\Omega_G_{n}</math> on tippudest, servadest ja "mitte-servadest" sümmetriline, st omab ühte tipu-, ühr serva- ja ühte "mitteserva" orbiiti.
 
2. [[Orbiitgraaf]]id on graafi <math>G</math> lõikumatud osised (alamgraafid).
46. rida:
4. Erinevate graafide orbiitgraafid <math>G_{n}</math> võivad olla ''isomorfsed või kattuda''.
 
5. Orbiitgraaf omab oma orbiitgraafi mis kujutab endast ''teist järku orbiitgraafiksorbiitgraafi'', neid järkusi võib olla rohkemgi.
 
6. Kõrgemat järku orbiitgraafid võivad olla isomorfsed või kattuda oma alamat järku orbiitgraafiga või ka lähtegraafiga <math>G</math>. Nende moodustumine on koonduv protsess.
54. rida:
== Tulemuste tähendusest ==
 
Graafi ''täielikku identifikaatorit'' või -''invarianti'', st identifikaatorit mis eristab graafi selle [[isomorfism]]i ja [[graafi sümmeetria|sümmeetriaomaduste]] täpsusega on otsitud juba aastakümneid, kuid needsee ei ole andnud soovitud tulemusi ning huvi nende vastu on raugenud. Lahendusi on püütud leida ka [[graafi kanooniline esitus|graafi kanoonilise esituse]] pinnal. Paraku ei sisalda niisugused esitused teavet graafi struktuuri ega selle sümmeetriaomaduste kohta.
 
Graafe osutus võimalikuks identifitseerida ja esitada nende elementaarsete sümmeetriaomaduste tuvastamise teel saadud [[struktuurimudel]]i või [[graafi seosmaatriks]]i astendamise näol, mis tuvastavad [[graafi struktuur]]i [[isomorfism]]i täpsusega Graafide identifitseerimine on [[struktuurisemiootika]] üks põhiprobleeme.
60. rida:
Maksimaalne arv <math>p</math> ühesuguste väärtustega astmeelemendid <math>e^n_{ij}</math> moodustavad tipupaaride ''ekvivalentsusklassi'', mida [[rühmateooria]] aspektist graafi [[graafi orbiit|''orbbiidiks'']] või ''transitiivsuspiirkonnaks'' nimetatakse. Sagedusvektorite <math>u_i</math> baasil korrastatud maatriksaste <math>E^n_{ord}</math> tuvastab ka tipuorbiidid. Struktuurses aspektist nimetatakse orbiite ''positsiooniklassideks'' ehk ''positsioonideks''.
 
Rühmateoreetilisest aspektist on graafi struktuuri ja sümmeetriaomadusi teadaolevalt varem uurinud tipuorbiitide tasemel vaid B. Weisfeiler <ref> B. Weisfeiler. '' On Construction and Identification of Graphs''. Springer Lect. Notes Math., 558, 1976 </ref>. Siin

Oluline on oluline, et ''rühmateoreetilise ja maatriksastme lähenemiste tulemused langevad kokku''. Selline [[graafide identifitseerimine|graafide identifitseerimise]] viis viib [[isomorfismiprobleem]]i ja [[Ulami hüpotees]]i selgitamiseni ning on seotud [[graafide süsteem]]ide moodustamisega.
 
== Vaata ka ==
Pärit leheküljelt "https://et.wikipedia.org/wiki/Graafide_identifitseerimine"