Erinevus lehekülje "Isomorfism" redaktsioonide vahel

Lisatud 751 baiti ,  9 aasta eest
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.
 
==Isomorfismiklassid ja kanooniline esitus==
[[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'''.
Isomorfismiklassid on graafiteooriad hästi rakendatavad. Isomorfismiklassi kuuluvatel graafidel on üks ja seesama struktuur. Seda struktuuri on võimalik esitada spetsiaalse [[struktuurisemiootika|struktuurse mudeli]] '''''S''''' abil <ref> J.-T. Tevet. 2009. Graafi semiootiliste invariantide müsteerium. ''S.E.R.R., Tallinn''. ISBN 9789949183319 </ref>. [[File:Equivalence.jpg|thumb|alt=Structural equivalence|Graafid ja nende struktuursed mudelid.]]
 
Erinevad graafid '''''G''''' ja '''''H''''' omavad ühesuguseid ehk ekvivalentseid struktuurseid mudeleid '''''S(G) ''''' ja '''''S(H)''''' ! See tähendab, et graafid on '''''isomorfsed''''' <math>G\simeq H</math> ehk nende '''''struktuurid on ekvivalentsed'''''. On tõestatud, et struktuursete mudelite moodustamise ja nende ekvivalentsuse fikseerimise ajaline keerukus on '''P''' <ref> A. Dharwadker, J.-T. Tevet. 2009. The Graph Isomorphism Algorithm. ''Proc. Institute of Mathematics'', Amazon Books, ISBN 9781466394374 </ref>.
 
==Isomorfismist erinevates valdkondades==
563

muudatust