Isomorfismiprobleem

Allikas: testwiki
Mine navigeerimisribale Mine otsikasti

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 [1], väites, et rühmade "struktuur" sarnanevat isomorfismiprobleemiga. Paraku jääb see sarnasus kõrvaltvaatajale raskelt tabatavaks. See probleem on seni lahendamata paljude oluliste algebra klasside puhul.

Graafide isomorfismi probleem

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 [2] 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 [3] ning G. Gati [4], kes tituleerisid isomorfismiharrastuse "isomorfismihaiguseks". Isomorfismiprobleem muutus vahepeal koguni tabuks. Selle probleemi sisulist käsitlemist väldivad oma graafiõpikutes paljud. Näiteks B. Bollobasi "Modern Graph Theory"[5] 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 kirjatööd, näiteks N. Chistofiedese [6] oma, ei sisalda mitte midagi isomorfismiga seostuvat. Kuid tegijaid leidub. Näiteks, seda on lahanud Netšepurenko jt [7] ning esitanud ka sellega seotud algoritme ja arvutiprogramme. L. Babai [8] leiab selleks Monte-Carlo algoritmi sobiva olevat. G. Tinhofer, M. Lödecke, S. Bauman ja L. Babel [9] , 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. Kobleri, H. Schöningi ja J. Torani monograafiat [10], kus käsitletakse seda ajalise keerukuse aspektist. Ka K. Thulasirman ja M. N. S. Swamy [11] ning S. Pemmaraju, S. Sciena [12] piirduvad isomorfismi puhul vaid keerukuseprobleemi esile toomisega.

Probleemi ajaline keerukus

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

Süstematiseerimine

Isomorfismi tuvastamise meetodite süstematiseerimine on viinud lihtsa skeemini: a) sorteerimise ja mittesorteerimise 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, soovitatavalt isomorfismi täpsusega. Kanoonilise esituse probleemi püstitas arvatavasti Lazlo Babai[15] 1977. aastal.

Frank Harary [16] 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 [17] on arvamusel, et see on lahendatav graafi tihedust, tsükleid, klikke jne iseloomustavate lokaalsete invariantide baasil.

Samas on isomorfismi mõiste ise sama hajuvaks muutunud nagu on juhtunud struktuuri mõistega. Klassikaliselt on isomorfism defineeritud kui "bijektsioon, mis säilitab naabrused". Hassler Whitney (1907–1989) leidis juba 1932. aastal, et "range isomorfism" on "bijektsioon, mis säilitab naabrused + veel midagi" [18]. Ülo Kaasik defineerib: "bijektsioon, mis säilitab struktuuri", mis on täiesti arusaadav, kuigi ta ei ole struktuuri määratlenud. Peale selle on isomorfism seotud ka struktuursete ekvivalentsusklasside ehk orbiitidega.

Isomorfismiklassid ja kanooniline esitus

Structural equivalence
Graafid ja nende struktuursed mudelid

Isomorfismiklassid on graafiteoorias hästi rakendatavad. Isomorfismiklassi kuuluvatel graafidel on üks ja seesama struktuur. Seda struktuuri on võimalik kanooniliselt esitada spetsiaalse semiootilise mudeli S abil [19][20].

Erinevad graafid G ja H omavad ühesuguseid ehk ekvivalentseid struktuurseid mudeleid SG ja SH ! See tähendab, et graafid on isomorfsed G≃H ehk nende struktuurid on ekvivalentsed. On tõestatud, et struktuursete mudelite moodustamise ja nende ekvivalentsuse fikseerimise ajaline keerukus on P [14].

Viited

Mall:Viited

Välislingid

  • [1] Algoritm graafi isomorfismi leidmiseks c# keeles.

es:Isomorfismo de grafos ru:Изоморфизм графов

  1. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega 9z2V9 on ilma tekstita.
  2. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega MlTjg on ilma tekstita.
  3. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega WS4M5 on ilma tekstita.
  4. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega gUcq2 on ilma tekstita.
  5. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega dKL8D on ilma tekstita.
  6. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega sZRPB on ilma tekstita.
  7. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega ZYrrs on ilma tekstita.
  8. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega Rt3Gn on ilma tekstita.
  9. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega X9fW7 on ilma tekstita.
  10. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega 35OX9 on ilma tekstita.
  11. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega njZSZ on ilma tekstita.
  12. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega 2isjU on ilma tekstita.
  13. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega Johnson 2005 on ilma tekstita.
  14. ↑ 14,0 14,1 Viitamistõrge: Vigane <ref>-silt. Viide nimega S1MXu on ilma tekstita.
  15. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega qjFg5 on ilma tekstita.
  16. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega k8uRS on ilma tekstita.
  17. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega pFWlz on ilma tekstita.
  18. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega oMELM on ilma tekstita.
  19. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega O7spZ on ilma tekstita.
  20. ↑ Viitamistõrge: Vigane <ref>-silt. Viide nimega aScVN on ilma tekstita.
Pärit leheküljelt "https://et.wiki.beta.math.wmflabs.org/w/index.php?title=Isomorfismiprobleem&oldid=863"