Erinevus lehekülje "Isomorfism" redaktsioonide vahel

Mõned algoritmilist graafiteooriat esitavad oopused, nagu N. Chistofiedese <ref> N. Christofides. 1975. Graph Theory: An algorithmic approach. ''Academic Press, N.Y., London, San Francisco'' </ref> oma, ei sisalda mitte midagi isomorfismiga seonduvat. Kuid tegijaid leidub. Näiteks, seda on lahanud Netšepurenko jt <ref> M. Нечепуренко и др. 1990. Алгоритмы и программы решение задач для графов и сетей. ''Новосибирск''. </ref> ning esitanud ka sellega seotud algoritme ja arvutiprogramme. L. Babai <ref> L. Babai. 1977. On the isomorphism problem. ''Unpublished manuscript'' </ref> leiab selleks Monte-Carlo algoritmi sobiva olevat. G. Tinhofer, M. Lödecke, S. Bauman ja L. Babel <ref> G. Tinhofer, M. Lödecke, S. Baumann, L. Babel. 1997. STABCOL, Graph Isomorphism Testing on the Weisfeiler-Leman Algorithm. </ref> , 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 <ref> G. Kobler, H. Schönig, J. Toran. 1993. The Graph Isomorphism Problem: Its Structural Complexity. </ref>, kus käsitletakse seda ajalise keerukuse aspektist. Ka K. Thulasirman ja M. N. S. Swamy <ref> K. Thulasiraman, M. N. S. Swamy. 1992 Graphs: Theory and Algorithms. ''John Wiley & Sons.'' </ref> ning S. Pemmaraju, S. Sciena <ref> S. Pemmaraju, S. Sciena.2003. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. ''Cambridge University Press'' </ref> piirduvad isomorfismi puhul vaid keerukuseprobleemi esile toomisega.
 
Aktuaalne ongi isomorfismiprobleemi käsitlemine [[algoritmiline keerukus|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 AE. Luksi (1983) algoritmi ajalise keerukusega 2<sup>O(√(''n''&nbsp;log&nbsp;''n''))</sup> ''n''-tipulise graafi puhul. <ref name="Johnson 2005">{{harvnb|Johnson|2005}}</ref>. Kuid neid on konstrueeritud ja tõestatud ka polünomiaalsetena '''P''' nagu seda on A. Dharwadkeri jt <ref> A. Dharwadker, J.-T. Tevet. 2009. The Graph Isomorphism Algorithm. ''Proc. Institute of Mathematics'', Amazon Books, ISBN 9781466394374 </ref>. 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.
[[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