Algoritmi i ri deshiofron problemet grafike.

Shkenca kompjuterike shpikja e njė dekade ndihmon nė identifikimin e rrjetave identike.

Njė mister ka ngatėrruar pėr njė kohė tė gjatė kompjuterat dhe shkencetarėt qė programojnė por tashmė gjithēka ėshtė bėrė mė e menaxhueshme.

Njė algoritėm i ri zgjidh nė mėnyrė efiēente problemet izomorfike tė grafeve, shkencėtari kompjuterik Lįszló Babai shpalli mė 10 Nėntor nė seminarin Combinatorics dhe Theoretical Computer Science nė Universitetin e Chicago. Problemi kėrkon qė tė pėrcaktohet nėse 2 sete tė ndara tė pikave ndėrlidhėse, tė njohura si grafe, janė tė lidhura nė tė njėjtėn mėnyrė edhe pse grafet duken shumė tė ndryshme. Nė praktikė, algoritmet ekzistuese mund ta bėjnė punėn nė njė kohė tė arsyeshme, por ishte e mundur qė grafet shumė komplekse tė bėjnė problemin tė vėshtirė pėr tu zgjidhur. Tashmė jo mė.

Algoritmi i sjellė nga Babai ka ende nevojė tė testohet dhe tė verifikohet, por ekspertiza e tij u dha kolegėve besim nė rezultat: Ai po pėrballej me problemin edhe mė parė kur ai po shkruante temėn e diplomės pėr doktoraturė nė vitin 1984. Edhe pse problemi mund tė duket abstrakt, ėshtė njė shembull i shquar i njė klase tė ēuditshme misteresh qė kompjuterat kanė njė zgjidhės problemesh dhe kompjuteri ėshtė i aftė tė pėrcaktojė nė mėnyrė tė shpejtė nėse zgjidhja e problemit ėshtė e saktė. Rezultati gjithashtu mund tė kumbojė pas shkencės sė kompjuterave, njėlloj siē kimia tregon nėse molekulat komplekse kanė strukturė tė njėjtė apo jo.

Nė terminologjinė matematikore, grafi ėshtė njė punė e pėlqyeshme pėr njė rrjet, lloji i diagramės qė pėrshkruan, pėr shembull, njė faqe tė shokėve nė Facebook ose pėrhapja e njė sėmundje. Ēdo pikė, ose nyje, ėshtė si njė top ping-pongu qė ėshtė i padallueshėm nga njė top tjetėr dhe qė lidh njė ose disa topa nė njė varg. Me njė organizim tė tillė ėshtė e lehtė tė bėsh dy grafe identike fillestare tė duken tė ndryshme duke ndryshuar topat pėrreth. Problemi me grafin izomorfik kėrkon nga kompjuteri tė ekzaminojė dy grafet qė mund tė duken shumė tė ndryshme dhe tė pėrcaktojnė nėse tė gjithė topat ndajnė tė njėjtat lidhje. Grafet qė ndajnė kėtė lidhje janė izomorfike.

Kompjuterat pėrgjithėsisht kanė pak problem pėr tė pėrcaktuar nėse grafet janė identike. Por edhe pėr algoritmet mė tė mira, ka njė skenar pėr rastet mė tė kėqija nė tė cilin koha e zgjidhjes rritet pothuajse nė mėnyrė eksponenciale dhe numri i nyjeve rritet.

Babai tregon se ka zhvilluar njė algoritėm qė vlerėson edhe grafet me tė vėshtira nė atė qė quhet koha quasipolynomial, tė cilėn shkencėtarėt kompjuterikė e konsiderojnė tė arsyeshme.