Uporaba Schreier-Simsovega algoritma za učinkovitejše računanje preiskovalne ekvivalenceSikošek, Lovro (Avtor) Fürst, Luka (Mentor) Schreier-Simsov algoritemteorija grupteorija grafovgeneratorjistabilizatorpokritjesimetrijeZa problem iskanja podgrafnega izomorfizma obstaja mnogo algoritmov, a le redki vključujejo uporabo simetrij iskanega grafa za optimizacijo iskanja. To je motiviralo definicijo preiskovalne ekvivalence, ki omogoča zmanjšanje iskalnega prostora z upoštevanjem simetrij grafa, vendar pa obstoječe metode za iskanje preiskovalno ekvivalentnih particij grupo simetrij grafa in njene podgrupe obdelujejo v eksplicitni predstavitvi, kar ni najbolj učinkovito. V tem diplomskem delu bomo predstavili rezultate in algoritme iz računske teorije grup, ki nam omogočajo prilagoditev obstoječih pristopov za bolj učinkovito delo z grupami. Eden izmed ključnih obravnavanih algoritmov je Schreier-Simsov algoritem. Opisali bomo, kako lahko obravnavane koncepte uporabimo za računanje struktur, ključnih za preiskovalno ekvivalenco, kot sta stabilizator in pokritje s permutacijami. Predstavili bomo tudi novo metodo računanja pokritja s permutacijami. Svoj prilagojen postopek za iskanje preiskovalno ekvivalentnih particij bomo primerjali z obstoječim postopkom na dveh družinah zelo simetričnih grafov in pokazali, da naš pristop bistveno zmanjša prostorsko zahtevnost algoritma.20252025-07-10 13:35:01Diplomsko delo/naloga170625sl