Uporaba preiskovalne ekvivalence za pohitritev sodobnih algoritmov za problem podgrafnega izomorfizmaKUHAR, JON (Avtor) Fürst, Luka (Mentor) podgrafni izomorfizemgrafpreiskovalna ekvivalencaalgoritemsimetrijaoptimizacijaPri problemu podgrafnega izomorfizma se ukvarjamo z iskanjem pojavitev podanega vzorčnega grafa v podanem tarčnem grafu. Gre za pomemben problem na področju analize grafov, saj nastopa v vseh panogah, kjer nas zanimajo vzorci v grafih, na primer v kemiji ali pri analizi socialnih omrežij. Ker pa je problem podgrafnega izomorfizma NP-poln, so raziskave usmerjene v iskanje algoritmov, ki dobro delujejo vsaj v večini praktičnih primerov. Kot se izkaže, pa so mnogi od teh algoritmov neučinkoviti pri vzorčnih grafih z velikim številom avtomorfizmov (simetrij). V diplomski nalogi bomo pokazali, kako je mogoče obstoječe algoritme pohitriti z uporabo preiskovalne ekvivalence, ekvivalenčne relacije na množici vozlišč grafa, ki temelji na množici avtomorfizmov. Na podlagi preiskovalne ekvivalence vzorčnega grafa je namreč mogoče definirati množico omejitev, s katerimi lahko zmanjšamo nabor kandidatnih preslikav, ki jih moramo obravnavati pri iskanju primerkov vzorčnega grafa v tarčnem grafu. Obstoječe algoritme za reševanje problema podgrafnega izomorfizma smo nadgradili tako, da uporabljajo preiskovalno ekvivalenco. Svoje razširitve smo na več javno dostopnih zbirkah grafov primerjali z izhodiščnimi algoritmi. Izboljšave algoritmov smo objavili v obliki javno dostopnega modula v okviru obstoječe knjižnice za reševanje problema podgrafnega izomorfizma.20232023-09-15 12:55:01Diplomsko delo/naloga150269VisID: 36694COBISS_ID: 168897795sl