Integracija problema izomorfnega podgrafa v sistem ALGatorRemec, Peter (Avtor) Mihelič, Jurij (Mentor) Dobravec, Tomaž (Komentor) grafpodgrafalgoritemizomorfizemALGatorračunalništvoračunalništvo in informatikauniverzitetni študijdiplomske nalogeV diplomskem delu obravnavamo problem podgrafnega izomorfizma in njegovo integracijo v sistem ALGator. Iskanje izomorfnih podgrafov je dandanes prisotno na večih znanstvenih področjih, zato se vseskozi pojavljajo novi algoritmi za reševanje problema. Podrobneje smo opisali Ullmannov algoritem, izboljšani Ullmannov algoritem in algoritem RI, ki je najnovejši izmed naštetih. Njihove implementacije, katere so primerne za iskanje izomorfizmov tako na usmerjenih kot neusmerjenih neoznačenih grafih, smo zaradi integracije v sistem ALGator napisali v programskem jeziku Java. Sistem je namenjen predvsem raziskovalcem na področju razvoja algoritmov, saj omogoča enostavno testiranje njihove učinkovitosti in analizo pridobljenih rezultatov. Funkcionalnosti sistema smo v praksi uporabili na izbranemu problemu. Poleg definicije problema smo v projekt v ALGator-ju vključili vse implementirane algoritme (izboljšani Ullmannov algoritem je podan v dveh različicah) in opazovali njihovo učinkovitost. Eksperiment smo izvedli na več kot 50000 različnih parih grafov. Z analizo rezultatov v ALGator-ju smo pokazali, da je algoritem RI v primerjavi z ostalimi tremi algoritmi najhitrejši. Na drugi strani se je najslabše izkazal Ullmannov algoritem, njegovi izboljšani različici pa sta se v določenih scenarijih celo približala algoritmu RI. Z integracijo problema v sistem ALGator smo predstavili njegove zmogljivosti in navedli predloge za izboljšave.[P. Remec]20152015-02-10 11:50:14Diplomsko delo/naloga30549sl