Isomorfism: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
Resümee puudub |
|||
79. rida:
==Isomorfismiklassid ja kanooniline esitus==
Isomorfismiklassid on graafiteooriad hästi rakendatavad. Isomorfismiklassi kuuluvatel graafidel on üks ja seesama struktuur. Seda struktuuri on võimalik kanooniliselt esitada spetsiaalse [[struktuurisemiootika|struktuurse mudeli]] '''''S''''' abil <ref> J.-T. Tevet. 2002. Isomorphism and Reconstructions of the Graphs: A constructive approach and development. ''S.E.R.R., Tallinn''. </ref> <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>.
| |||