Graafi kanooniline esitus

Graafi kanooniline esitus (inglise: graph canonization) on graafi esitus mingil kaudsel, mitmesuguseid invariante kasutaval viisil – soovitatavalt isomorfismi täpsusega. Graafi kanoonilist esitust võib nimetada ka graafi identifitseerimiseks.

Kanoonilise esituse probleemi püstitas Lazlo Babai  L. Babai. 1983. Canonical labelling of graphs. – Proc. 15th ACM Symposium on Theory Computing 171–183.  1977. aastal.

Frank Harary F. Harary. 1972. Graph Theory. Addison-Wesley. ISBN 0201027879  järgi on kanooniline esitus võimalik globaalinvariantide (polünoomid, spektrid jt) täieliku süsteemi baasil. A. Zõkov  A. Зыков. 1987. Основы теории графов. Наука. on arvamusel, et see on lahendatav graafi tihedust, tsükleid, klikke jne iseloomustavate lokaalsete invariantide baasil. S. Locke http//:www.math.fau.edu/locke/isotest leiab, et isomorfismi testimiseks sobivad hästi kahendsüsteemis esitatud ülipikad 3-kuup-koodid. Kanooniliste vormide otsingud on jätkuvalt aktuaalsed  Y. Gurevich. From Invariants to Canonization. – The Bull. of Euro. Assoc. for Comp. Sci., No. 63, 1997 . Paraku ei sisalda niisugused esitused teavet graafi struktuuri ega selle sümmeetriaomaduste kohta.

Graafi kanooniline esitus graafi seosmaatriksi astendamise baasil

pisi|Identification of graphs by exponantation the adjacency matrix

Tipupaarid graafi lähte seosmaatriksis  moodustavad vaid kaks klassi: servade ja mitteservade klassi. Seosmaatriksi korrutamisel iseendaga,  suureneb klasside arv  ja see jätkub teatud astmeni  ning lõppeb siis. Klassi identifikaatoriteks on ühesuguste väärtustega elemendid  korrutises . Oluline on, et maksimaalse arvu  korral identifitseeritakse kõik tipupaari klassid. 

Tipupaari klassid langevad kokku graafi  tipupaari orbiitidega (see on rühmateooria mõiste). Kontranäiteid ei ole tuvastatud. See fakt vajab tõestamist või ümberlükkamist. Tipuorbiidid tulevad ilmsiks korrutise   korrastamise käigus..

Identifikaatorite  väärtused on järjestatavad jadaks  … . Saadud korrutise  igale reale  kinnistada vector  mis esitab tipupaari klasside arvu selles reas. Kõikide ridade   ja veergude  leksikograafiline ümberjärjestamine vektorite   põhjal korrutises  moodustab korrastatud korrutise  mis esitab kõik tipupaaride- ja tippude orbiidid. See kujutab endast isomorfsete graafide printsipiaalset invarianti John-Tagore Tevet. (2014). Semiotic modeling of the structure. ISBN 9871503367456. Amazon Books ..

Ka graafi semiootiline mudel on aga selline kanooniline esitis, mis kujutab endast isomorfsete graafide olulist invarianti ning esitab nii graafi struktuuri kui ka selle sümmeetriaomadusi J.-T. Tevet. Graafide identifitseerimine. S.E.R.R., Tallinn, 2017 ISBN 9789949816514 . 

 Vaata ka 

Graafi struktuur

Graafide identifitseerimine

= Välislingid 

 Identification and systemization of the graphs (pdf)

Viited 


Kategooria:Graafiteooria