Erinevus lehekülje "Isomorfism" redaktsioonide vahel

Mine navigeerimisribale Mine otsikasti
Eemaldatud 1 bait ,  9 aasta eest
[[Invariant]]idele rajatud meetodid on viinud isomorfismi tuvastamise graafide ''kanoonilise esituse'' tasemele, mis tähendab graafi kujutamist mingil selle struktuuri esitaval kujul, soovitavalt isomorfismi täpsusega. Kanoonilise esituse probleemi püstitas arvatavasti 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> Frank Harary. 1969. Graph Theory. ''Addison-Wesley''. </ref> järgi on isomorfismiprobleem lahendatav globaalinvariantide (polünoomid, spektrid jt) täieliku süsteemi baasil. S. Locke (http//:www.math.fau.edu/locke/isotest ) leiab, et isomorfismi testimiseks sobivad hästi kahendsüsteemis esitatud ülipikad 3-kuup-koodid. A. Zõkov <ref> A. Зыков. 1987. Основы теории графов. ''Наука'' </ref> on arvamusel, et see on lahendatav graafi tihedust, tsükleid, klikke jne iseloomustavate lokaalsete invariantide baasil.
 
[[Struktuurisemiootika]]s on graafid ''G'' ja ''H'' isomorfsed parajast siis kui need omavad ühte ja sama struktuuri, st kui vastavad semiootilised mudelid on ekvivalentsed. On tõestatud, et nii semiootiliste mudelite moodustamine kui ka nende ekvivalentsuse tuvastamine on '''P'''.
563

muudatust

Navigeerimismenüü