Graafi kanooniline esitus: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
Poolelijäänud täiendus |
täiendatud |
||
4. rida:
Frank Harary <ref>F. Harary. 1972. ''Graph Theory''. Addison-Wesley. ISBN 0201027879 </ref> järgi on kanooniline esitus võimalik globaalinvariantide ([[polünoom]]id, [[spekter|spektrid]] jt) täieliku süsteemi baasil. A. Zõkov <ref> A. Зыков. 1987. ''Основы теории графов''. Наука.</ref> on arvamusel, et see on lahendatav graafi tihedust, tsükleid, klikke jne iseloomustavate lokaalsete invariantide baasil. S. Locke <ref>http//:www.math.fau.edu/locke/isotest</ref> leiab, et isomorfismi testimiseks sobivad hästi kahendsüsteemis esitatud ülipikad 3-kuup-koodid. Kanooniliste vormide otsingud on jätkuvalt aktuaalsed <ref> Y. Gurevich. ''From Invariants to Canonization''. – The Bull. of Euro. Assoc. for Comp. Sci., No. 63, 1997 </ref>. Paraku ei sisalda niisugused esitused teavet graafi struktuuri ega selle sümmeetriaomaduste kohta.
==Graafi kanooniline esitus [[seosmaatriks]]i [[astendamine|astendamise]] baasil==
Tipupaarid graafi lähte seosmaatriksis <math>E^1</math> moodustavad vaid kaks klassi: servade ja mitteservade klassi. Seosmaatriksi korrutamisel iseendaga, <math>E^1\cdot E^1=E^2</math> suureneb klasside arv <math>p</math> ja see jätkub teatud astmeni <math>E^n</math> ning lõppeb siis. Klassi identifikaatoriteks on ühesuguste väärtustega elemendid <math>e^n_{i,j}</math> korrutises <math>E^n</math>. Oluline on, et maksimaalse arvu <math>p</math> korral identifitseeritakse kõik tipupaari klassid.
[[File:STRUSKAN.jpg|pisi|Graph canonization by exponentation the adjacency matrix]]
Tipupaari klassid langevad kokku graafi <math>G</math> tipupaari [[orbiit]]idega (see on [[rühmateooria]] mõiste). Kontranäiteid ei ole tuvastatud. See fakt vajab tõestamist või ümberlükkamist. Tipuorbiidid tulevad ilmsiks korrutise <math>E^n</math> korrastamise käigus..
[[struktuurisemiootika|Graafi semiootiline mudel]] on aga selline kanooniline esitis, mis kujutab endast [[isomorfism|isomorfsete graafide]] täielikku [[invariant]]i ning esitab nii [[graafi struktuur]]i kui ka selle [[graafi sümmeetria|sümmeetriaomadusi]] <ref>J.-T. Tevet. ''Graafide identifitseerimine''. S.E.R.R., Tallinn, 2017 ISBN 9789949816514 </ref>. ▼
Identifikaatorite <math>e^n_{i,j}</math> väärtused on järjestatavad jadaks <math>S^n_p=e^n_{1}< e^n_{2}< </math> … <math> < e^n_{p}</math>. Saadud korrutise <math>E^n</math> igale reale <math>i</math> kinnistada vector <math>u^n_i</math> mis esitab tipupaari klasside arvu selles reas. Kõikide ridade <math>i</math> ja veergude <math>j</math> leksikograafiline ümberjärjestamine vektorite <math>u^n_i</math> põhjal korrutises <math>E^n</math> moodustab korrastatud korrutise <math>E^n_ord</math> mis esitab kõik tipupaaride- ja tippude orbiidid. See kujutab endast isomorfsete graafide [[täielik invariant|täielikku invarianti <ref> John-Tagore Tevet. (2014). ''Semiotic modeling of the structure''. ISBN 9871503367456. Amazon Books </ref>..
▲Ka [[struktuurisemiootika|
==Viited==
| |||