Graafide identifitseerimine

Allikas: Vikipeedia
Jump to navigation Jump to search

Graafide identifitseerimine tähendab graafide eristamist, äratundmist või samastamist neist tuletatud invariantide põhjal mitmesuguste koodide, vektorite, polünoomide, spektrite jt. näol.

Graafi täieliku identifikaatori otsingutest[muuda | muuda lähteteksti]

Graafi täielikku identifikaatorit või -invarianti, st identifikaatorit mis eristab graafi selle isomorfismi ja sümmeetriaomaduste täpsusega on otsitud juba aastakümneid, kuid need ei ole andnud soovitud tulemusi ning huvi nende vastu on raugenud. Lahendusi on püütud leida ka graafi kanoonilise esituse pinnal [1]. 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 struktuurimudeli või graafi seosmaatriksi astendamise näol, mis tuvastavad graafi struktuuri isomorfismi täpsusega [2]. Graafide identifitseerimine on struktuurisemiootika üks põhiprobleeme.

Graafi identifitseerimine tipupaaride baasil[muuda | muuda lähteteksti]

Identification of graphs by exponantation the adjacency matrix

Graafi elementaarosised on tipupaarid (mitte tipud) ja selle elementaarsed sümmeetriaosised on aga tipupaaride ekvivalentsus- ehk sümmeetriaklassid, mida rühmateooria aspektist orbiitideks ja struktuursest aspektist positsioonideks nimetatakse. Graafi struktuurimudeli puhul identifitseeritakse tipupaare (täpsemalt: tipupaaride vahelisi suhteid) nende ümbruste ühisosa iseloomustavate invariantide baasil [3].

Graafi seosmaatriksi astendamise teel tuvastatakse graafi struktuursed ja sümmeetria omadused [4] [5]. Nende tuvastamine rajaneb graafi elementaarosiste – tipupaaride – identifitseerimisele. Graafi seosmaatriksite astendamise puhul teatud astmeni eristavad selle elementide erinevad väärtused vastavaid sümmeetriaklasse.

Korrutada algne graafi seosmaatriks iseendaga, kus ja . Iga astme korral suureneb reeglina tipupaare iseloomustavate astmeelementide erinevate väärtuste arv . Moodustada nende erinevate väärtuste jada . Kui astme korral erinevate väärtuste arv enam ei suurene, siis peatada korrutamine ja moodustada väärtuste jada baasil igale reale vastav väärtuste sagedusvektor . Järjestada (transponeerida) saadud maatriksastme read ja veerud leksikograafiliselt vastavalt nende sagedusvektoritele . Saame korrastatud maatriksastme . Salvestada maatriksaste ja selle korrastatud maatriksaste .

Nii struktuurimudel kui ka maatriksaste on võrdväärsed, teineteist täiendavad graafide identifitseerimise atribuudid. Kuigi eristab ja esitab tippudevahelisi suhteid küllaltki täpselt, võivad need osutuda vahest mittetäielikeks invariantideks. elemendid on küll täielikud invariandid, kuid ei erista omavahel graafi servi ega nende puudumist.

Orbiitide (positsiooniklasside) põhiomadused[muuda | muuda lähteteksti]

1. Kui graafi tipud kuuluvad samasse positsiooni (orbiiti) siis on alamgraafid isomorfsed.

2. Kui graafi servad kuuluvad samasse positsiooni (orbiiti) siis on alamgraafid isomorfsed.

3. Kui graafi mitteservad kuuluvad samasse positsiooni (orbiiti) siis on ülemgraafid isomorfsed.

Tipupaari-orbiitide baasil saadud isomorfsed alamgraafid kujutavad endast graafi naaber alamstruktuuri ja/või naaber ülemstruktuuri. Kõikide n tipuliste naaberstruktuuride jadade parv tühistruktuuri ja täisstruktuuri vahel moodustab n-tipuliste graafide süsteemi. Selle süsteemi graafe võime omakorda kujutada tippudena ja nendevahelisi naabrusi 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 seosest nende vahel; kuuetipuliste süsteem koosneb 156 struktuurist ja 572 seoaest nende vahel, jne. Kõik see on seotud ülemineku tõenäosuste ja ka Ulami hüpoteesiga serva-eralduste aspektist.

Graaf mis koosneb orbiiti kuuluvatest servadest nimetatakse orbiitgraafiks .

Orbiitgraafide omadusi[muuda | muuda lähteteksti]

1. Orbiitgraaf on tippudest, servadest ja "mitte-servadest" sümmetriline, st omab ühte tipu-, ühr serva- ja ühte "mitteserva" orbiiti.

2. Orbiitgraafid on graafi lõikumatud osised (alamgraafid).

3. Mõned orbiitgraafid võivad olla isomorfsed oma lähtegraafiga (näiteks, kuubi üks orbiitgraafidest on kuup)..

4. Erinevate graafide orbiitgraafid võivad olla isomorfsed või kattuda.

5. Orbiitgraaf omab oma orbiitgraafi mis kujutab endast teist järku orbiitgraafiks, 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 . Nende moodustumine on koonduv protsess.

Orbiitgraahid avavad lähtegraafi varjatud külgi. Näiteks Folkmani graafi üks orbiitgraaf on Peterseni graaf. .Orbiitgraafid avavad erinavate graafide ühesuguseid osiseid. Hüperkuup ja Möbius-Kantori graaf omavad ühesuguseid orbiitgraafe, jne. Orbiitgraafid on olulised vahendid graafi struktuuri ja sümmaatriaomaduste tuvastamisel.

Tulemuste tähendusest[muuda | muuda lähteteksti]

Maksimaalne arv ühesuguste väärtustega astmeelemendid moodustavad tipupaaride ekvivalentsusklassi, mida rühmateooria aspektist graafi orbbiidiks või transitiivsuspiirkonnaks nimetatakse. Sagedusvektorite baasil korrastatud maatriksaste 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 [6]. Siin on oluline, et rühmateoreetilise ja maatriksastme lähenemiste tulemused langevad kokku. Selline graafide identifitseerimise viis viib isomorfismiprobleemi ja Ulami hüpoteesi selgitamiseni ning on seotud graafide süsteemide moodustamisega.

Vaata ka[muuda | muuda lähteteksti]

Viited[muuda | muuda lähteteksti]

  1. Y. Gurevich. From Invariants to Canonization. – The Bull. of Euro. Assoc. for Comp. Sci., No. 63, 1997
  2. J.-T. Tevet. Graafide identifitseerimine. S.E.R.R., Tallinn, 2017 ISBN 9789949816514
  3. J.-T. Tevet. Graafide varjatud külgi. S.E.R.R., Tallinn, 2010 ISBN 9789949213108
  4. J.-T. Tevet. Semiotic Modelling of the Structure. ISBN 9781503367456, 2014, Amazon Books
  5. J.-T. Tevet. Graafide identifitseerimine. ISBN 9789949816514, 2017, S.E.R.R., Tallinn
  6. B. Weisfeiler. On Construction and Identification of Graphs. Springer Lect. Notes Math., 558, 1976