Isomorfism: erinevus redaktsioonide vahel

Eemaldatud sisu Lisatud sisu

Reasisene

Redaktsioon: 5. november 2011, kell 17:52

See artikkel räägib filosoofia ja matemaatika mõistest; mineraloogia mõiste kohta vaata artiklit Isomorfism (mineraloogia)

Isomorfism (kreeka: ἴσος isos – ühesugune, ja μορφή morphe – vorm) moodustavad koos homomorfismiga filosoofilise kategooria, mis iseloomustab vastavust objektide struktuuride vahel ^[1] ^[2].

Mõned spetsiifilise suunitlusega filosoofilised koolkonnad võivad mitte tunnistada nende mõistete kuulumist kategooriate kilda.

Selgitus

Isomorfism tähendab vastavust, kus kaks süsteemi, vaadelduna lahus neid moodustavate elementide loomusest, vastab esimese süsteemi igale elemendile ainult üks teise süsteemi element ning ühe süsteemi igale seosele vastab ainult üks seos teises – ja vastupidi. Seega saab isomorfismist rääkida vaid niisuguste objektide puhul, millel on struktuur, st on määratletud selle elemendid (komponendid, osised) ja nendevahelised seosed (suhted).

Isomorfism on määratletav kui struktuuri säilitav üks-ühene vastavus objektide vahel. Isomorfsete objektide hulk moodustab isomorfismiklassi.

Teadaolevalt võttis isomorfismi termini kasutusele 1857. aastal A. Cayley oma keemiliste isomeeride alastes uuringutes ^[3]. Kõige piltlikum näide isomorfismist on graafide isomorfism.

Kaks graafi on isomorfsed, st omavad ühesugust struktuuri, vaatamata nende erinavaele „välimusele“.

Graaf G	Graaf H	Isomorfism G ja H vahel
		ƒ(a) = 1 ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7

Isomorfism matemaatikas

Matemaatikas defineeritakse isomorfismi kui süsteemi niisugust üks-ühest kujutust sama tüüpi süsteemiks, mille korral säilib süsteemide struktuur. Näiteks, kujund ja selle kujundi matemaatiline avaldis.

Isomorfism on pööratav morfism, millel on pöördmorfism, kus nende korrutis on ühikmorfism. Topoloogilist isomorfismi nimetatakse homoömorfismiks.

Algebras on isomorfism kujutus objektide vahel mis näitab suhet kahe omaduse või operatsiooni vahel. Kui kahe struktuuri vahel esineb isomorfism, siis öeldakse, et vastavad objektid on isomorfsed. Teatud mõttes on isomorfsed objektid struktuurselt samased, kui muud liiki erinevused on ignoreeritud. Veelgi formaalsemalt on isomorfism bijektiivne kujutus f niisugune, et f ja selle pöördfunktsioon f⁻¹ on struktuuri säilitavad kujutused kahe algebralise struktuuri vahel, st need mõlemad on homomorfsed. Isomorfism on algebras samalaadselt defineeritud ka rühma, ringi ja teiste struktuuride kohta.

Isomorfism graafiteoorias tähendab graafide G ja H struktuuri säilitavat tippude bijektsiooni

f\colon V(G)\to V(H)\,\!

niisugust, et kui graafi G mingid kaks tippu u ja v on seotud, siis ja ainult siis on ƒ(u) ja ƒ(v) seotud garaafis H.

Selle näide on selgituses esitatud. Oluline on siin nende substitutsioonide väljatoomine: ${\begin{pmatrix}a&b&c&d&g&h&i&j\\1&6&8&3&5&2&4&7\end{pmatrix}}$

Kahe graafi isomorfsust tähistatakse $G\simeq H$ . Juhul kui bijektsioon on graafi kujutus iseendasse, st kui G ja H on üks ja sama graaf, siis seda bijektsiooni nimetatakse graafi G automorfismiks AutG.

Graafide isomorfism on ekvivalentsussuhe ning graafe võib klassifitseerida ekvivalentsusklassideks. Isomorfsete graafide hulka nimetatakse graafide isomorfismiklassiks.

Isomorfismiprobleem

Isomorfismiprobleemiks nimetatakse ülesannet konstrueerida efektiivne algoritm, mis antud klassi kahe suvalise algebralise süsteemi korral selgitab, kas nad on isomorfsed või mitte. Isomorfismiprobleemi on rühmateooria seisukohalt käsitlenud C. Hoffman ^[4] väites, et rühmade „struktuur” sarnanevat isomorfismiprobleemile. Paraku jääb see sarnasus kõrvaltvaatajale raskelt tabatavaks. See probleem on seni lahendamata paljude oluliste algebra klasside puhul.

Eriline roll on isomorfismiprobleemil graafide vallas. Selle põhimõtteline teoreetiline algoritm täiesti olemas – see seisneb graafi H seosmaatriksi ridade ja nendele vastavate veergude ümberpaigutamises (permuteerimises, ümberjärjestamises, ümbervahetamises) niikaua, kui see ei lange kokku graafi G seosmaatriksiga. Sellel on üks oluline puudus – see on väga mahukas (keeruline), selle sammude arv läheneb n! (n-faktoriaalini). Omal ajal arvati, et 16! permutatsiooni arvutamine võtaks aega kuni 40 aastat.

Hakati otsima teisi teid graafide isomorfismi tuvastamiseks, mis oli aastail 1970-1980 väga populaarne. Näiteks, S. Toida ^[5] pakkus selleks tõsimeeli välja „kauguste maatriksi“. Tõepoolest on graafi kaugustemaatriksid omavahel kergemini eristatavad kui seosmaatriksid. Graafide mitteisomorfismi võib nende abil tuvastada „peaaegu alati“, ka isomorfismi tuvastamine võib vahel korda minna.

Selle perioodi algoritme on kriitiliselt analüüsinud R. C. Read ja D. G. Corneil ^[6] ning G. Gati ^[7], kes tituleerisid isomorfismiharrastuse „isomorfismihaiguseks“. Isomorfismiprobleem muutus vahepeal koguni tabuks. Selle probleemi sisulist käsitlemist väldivad oma graafiõpikutes paljud. Näiteks B. Bollobas´i „Modern Graph Theory“^[8] on isomorfismi-probleemile pühendanud vaid kaks sõna, selles käsitletakse peamiselt „praktilisi“ probleeme nagu vooge võrkudes jne. Siiski tuuakse graafide isomorfismi visuaalne näide ära peaaegu kõikides graafiõpikutes – ja sellega enamasti piirdutaksegi.

Mõned algoritmilist graafiteooriat esitavad oopused, nagu N. Chistofiedese ^[9] oma, ei sisalda mitte midagi isomorfismiga seonduvat. Kuid tegijaid leidub. Näiteks, seda on lahanud Netšepurenko jt ^[10] ning esitanud ka sellega seotud algoritme ja arvutiprogramme. L. Babai ^[11] leiab selleks Monte-Carlo algoritmi sobiva olevat. G. Tinhofer, M. Lödecke, S. Bauman ja L. Babel ^[12] , väidavad, et isomorfismi probleem on lahendatav Weisfeiler-Lehmani algoritmi abil. C. V. Raj ja M. S. Shivakumar loendavad mitmesuguseid spetsiifilisi atribuute selle probleemi lahendamiseks. Tuleb ära märkida G. Kobler´i, H. Schöning´i ja J. Toran´i monogaafiat ^[13], kus käsitletakse seda ajalise keerukuse aspektist. Ka K. Thulasirman ja M. N. S. Swamy ^[14] ning S. Pemmaraju, S. Sciena ^[15] piirduvad isomorfismi puhul vaid keerukuseprobleemi esile toomisega.

Aktuaalne ongi isomorfismiprobleemi käsitlemine ajalise keerukuse (inglise time complexity) seisukohalt. Levinud on arvamus, et see on mitte-polünomiaalne NP (inglise non-polynomial) ning praeguse aja „ametlik arvamus“ peab parimaks A. Luksi (1983) algoritmi ajalise keerukusega 2^{O(√(n log n))} n-tipulise graafi puhul.^[16]. Kuid neid on konstrueeritud ja tõestatud ka polünomiaalsetena P nagu seda on A. Dharwadkeri jt ^[17]. oma. Paljudel juhtudel pole see aga tõestatud. Diskussioonid keerukuse teemal kestavad.

Isomorfismi tuvastamise meetodite süstematiseerimine on viinud lihtsa skeemini: a) sorteerimise ja mitte-sorteerimis meetodid; b) lokaalsete ja globaalsete invariantide kasutamise meetodid.

Invariantidele 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 ^[18] 1977. aastal.

Frank Harary ^[19] järgi on isomorfismiprobleem lahendatav globaalinvariantide (polünoomid, spektrid jt) täieliku süsteemi baasil. S. Locke (* www.math.fau.edu/locke/isotest. ) leiab, et isomorfismi testimiseks sobivad hästi kahendsüsteemis esitatud ülipikad 3-kuup-koodid. A. Zõkov ^[20] on arvamusel, et see on lahendatav graafi tihedust, tsükleid, klikke jne iseloomustavate lokaalsete invariantide baasil.

Struktuurisemiootikas 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.

Isomorfismist erinevates valdkondades

Isomorfismi mõistet kasutatakse ka geoloogias, bioloogias, füüsikas jm. Korrektne on seda kasutada vaid seal, kus nende spetsiifiliste objektide struktuur ja bijektsioon on määratletav. See tähendab, kui nende geoloogiliste (bioloogilidte, füüsikaliste jt) süsteemide elemendid (komponendid, osised) ja nendevahelised seosed (suhted) on määratletud. Tegelikkuses sellest alati kinni ei peeta.

Viited

↑ Schmitd, Heirich, 1991. Philosophisches Wörerbuch. Stuttgard.
↑ Новая филосовская энциклопкдив. 2001, Москва. ISBN 5-244-00961-3 (00962-1)
↑ A. Cayley, 1857. On the theory of the analytical forms called trees. Phil. Mag. (4) 13 (1857), 172-176
↑ C. Hoffman. 1982. Group-Theoretic Algorithms and Graph Isomorphism. Springer.
↑ S. Toida. Isomorphism of graphs. 1973. – Proc. 16th Midwest Symp. Circuit Theory, Waterloo, 1973, XVI. 5.1-5.7.
↑ Read, R. C., Corneil, D. G., 1977. The graph isomorphism disease. J. of Graph Theory, 1 (1977), 339-363.
↑ Gati, G., 1978. Further annotated bibliography on the isomorphism disease. J. of Graph Theory, 3 (1979), 95-109.
↑ B. Bollobás. Modern Graph Theory. 1998. Springer.
↑ N. Christofides. 1975. Graph Theory: An algorithmic approach. Academic Press, N.Y., London, San Francisco
↑ M. Нечепуренко и др. 1990. Алгоритмы и программы решение задач для графов и сетей. Новосибирск.
↑ L. Babai. 1977. On the isomorphism problem. Unpublished manuscript
↑ G. Tinhofer, M. Lödecke, S. Baumann, L. Babel. 1997. STABCOL, Graph Isomorphism Testing on the Weisfeiler-Leman Algorithm.
↑ G. Kobler, H. Schönig, J. Toran. 1993. The Graph Isomorphism Problem: Its Structural Complexity.
↑ K. Thulasiraman, M. N. S. Swamy. 1992 Graphs: Theory and Algorithms. John Wiley & Sons.
↑ S. Pemmaraju, S. Sciena.2003. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press
↑ Johnson 2005
↑ A. Dharwadker, J.-T. Tevet. 2009. The Graph Isomorphism Algorithm. Proc. Institute of Mathematics, Amazon Books, ISBN 9781466394374
↑ L. Babai. 1983. Canonical labelling of graphs. – Proc. 15th ACM Symposium on Theory Computing 171-183.
↑ Frank Harary. 1969. Graph Theory. Addison-Wesley.
↑ A. Зыков. 1987. Основы теории графов. Наука

Vaata ka

Filosoofia leksikon. 1985. Tallinn.
Семёнов, A. Л., 1979. Изоморфизм. Математическая энциклопедия, Том 2, Москва.
McGraw-Hill dictionary of Mathematics, 1997. N. Y., ISBN 007524335.

[1] Schmitd, Heirich, 1991. Philosophisches Wörerbuch. Stuttgard.

[2] Новая филосовская энциклопкдив. 2001, Москва. ISBN 5-244-00961-3 (00962-1)

[3] A. Cayley, 1857. On the theory of the analytical forms called trees. Phil. Mag. (4) 13 (1857), 172-176

[4] C. Hoffman. 1982. Group-Theoretic Algorithms and Graph Isomorphism. Springer.

[5] S. Toida. Isomorphism of graphs. 1973. – Proc. 16th Midwest Symp. Circuit Theory, Waterloo, 1973, XVI. 5.1-5.7.

[6] Read, R. C., Corneil, D. G., 1977. The graph isomorphism disease. J. of Graph Theory, 1 (1977), 339-363.

[7] Gati, G., 1978. Further annotated bibliography on the isomorphism disease. J. of Graph Theory, 3 (1979), 95-109.

[8] B. Bollobás. Modern Graph Theory. 1998. Springer.

[9] N. Christofides. 1975. Graph Theory: An algorithmic approach. Academic Press, N.Y., London, San Francisco

[10] M. Нечепуренко и др. 1990. Алгоритмы и программы решение задач для графов и сетей. Новосибирск.

[11] L. Babai. 1977. On the isomorphism problem. Unpublished manuscript

[12] G. Tinhofer, M. Lödecke, S. Baumann, L. Babel. 1997. STABCOL, Graph Isomorphism Testing on the Weisfeiler-Leman Algorithm.

[13] G. Kobler, H. Schönig, J. Toran. 1993. The Graph Isomorphism Problem: Its Structural Complexity.

[14] K. Thulasiraman, M. N. S. Swamy. 1992 Graphs: Theory and Algorithms. John Wiley & Sons.

[15] S. Pemmaraju, S. Sciena.2003. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press

[Johnson_2005-16] Johnson 2005

[17] A. Dharwadker, J.-T. Tevet. 2009. The Graph Isomorphism Algorithm. Proc. Institute of Mathematics, Amazon Books, ISBN 9781466394374

[18] L. Babai. 1983. Canonical labelling of graphs. – Proc. 15th ACM Symposium on Theory Computing 171-183.

[19] Frank Harary. 1969. Graph Theory. Addison-Wesley.

[20] A. Зыков. 1987. Основы теории графов. Наука

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

@@ 45. rida: / 45. rida: @@
 [[Algebra]]s on isomorfism kujutus objektide vahel mis näitab suhet kahe omaduse või operatsiooni vahel.&nbsp; Kui kahe struktuuri vahel esineb isomorfism, siis öeldakse, et vastavad objektid on ''isomorfsed''.&nbsp; Teatud mõttes on isomorfsed objektid ''struktuurselt samased'', kui muud liiki erinevused on ignoreeritud.&nbsp; Veelgi formaalsemalt on isomorfism ''bijektiivne kujutus'' ''f'' niisugune, et ''f'' ja selle pöördfunktsioon ''f''<sup>&nbsp;&minus;1</sup> on struktuuri säilitavad kujutused kahe algebralise struktuuri vahel, st need mõlemad on [[homomorfism|homomorfsed]]. Isomorfism on algebras samalaadselt defineeritud ka [[rühm]]a, [[ring]]i ja teiste struktuuride kohta.
-''Kategooria teoorias'' on isomorfism [[morfism]] {{nowrap|''f'': ''X'' → ''Y''}}, mille ''inversiooni'' {{nowrap|''f''<sup> &minus;1</sup>: ''Y'' → ''X'',}} puhul {{nowrap|''f''<sup> &minus;1</sup>''f'' {{=}} [[identity function|id]]<sub>X</sub>}} ja {{nowrap|''f f''<sup> &minus;1</sup> {{=}} id<sub>Y</sub>.}}
 Isomorfism [[graafiteooria]]s tähendab graafide ''G'' ja ''H'' struktuuri säilitavat tippude bijektsiooni