Graafi kanooniline esitus: erinevus redaktsioonide vahel

Eemaldatud sisu Lisatud sisu
Legobot (arutelu | kaastöö)
P Robot: muudetud 1 intervikilinki, mis on nüüd andmekogus Wikidata
PResümee puudub
1. rida:
'''Graafi kanooniline esitus''' (inglise: ''graph canonization'') on [[graaf]]i esitus mingil kaudsel, mitmesuguseid [[invariant]]e kasutaval viisil – soovitavalt [[isomorfism]]i täpsusega.
 
Kanoonilise esituse probleemi püstitas Lazlo Babai <ref> L. Babai. 1983. Canonical labelling of graphs. – ''Proc. 15th ACM Symposium on Theory Computing'' 171–183. </ref> 1977. aastal.
 
Frank Harary<ref> FrankF. Harary. 19691972. ''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.
 
Paraku[[Graafi eistruktuur|Graafi sisaldasemiootiline niisugusedmudel]] esitusedaga teavetkujutab endast niisugust kanoonilist esitist mis esitab nii [[graafi [[struktuur]]i jakui ka selle [[graafi sümmeetria|sümmeetriaomadustesümmeetria omadusi]] kohta.
 
==Viited==