Metode barvnega označevanja za iskanje izomorfnih podgrafovArnšek, Tit (Avtor) Čibej, Uroš (Mentor) barvno označevanjeizomorfizem podgrafovalgoritmi na grafihMagistrsko delo obravnava metodo barvnega označevanja, algoritemsko tehniko za reševanje problema izomorfizma podgrafov. Ta problem, ki je NP-poln, se pojavlja v računalniškem vidu, bioinformatiki, kemoinformatiki in podatkovnem rudarjenju. Delo se uvodoma osredotoča na teoretične osnove problema izomorfizma podgrafov in njegovo parametrizirano kompleksnost, nato pa podrobno predstavi metodo barvnega označevanja, ki so jo leta 1994 razvili Noga Alon, Raphael Yuster in Uri Zwick. V osrednjem delu so analizirane različne tehnike znotraj barvnega označevanja: metoda naključnih orientacij, metoda naključnih barvanj in derandomizacija omenjenih algoritmov. Posebna pozornost je namenjena iskanju vozlišč barvitih poti s konceptom prič v množenju matrik. Delo raziskuje tudi razširitev metode na iskanje dreves in kompleksnejših podgrafov z omejeno drevesno širino. Predstavljena je povezava med barvnim označevanjem in degeneriranostjo grafov s poudarkom na minorsko zaprtih družinah grafov, kjer je predstavljena metoda za iskanje ciklov. V zaključku so predstavljene napredne strategije za izboljšanje metode, vključno z barvanjem po intervalih, metodo razvrščanja in premikanja, tehniko reprezentativnih množic in metodo deli in barvaj. Delo vključuje tudi eksperimentalno analizo, kjer so rezultati meritev različnih algoritmov barvnega označevanja in drugih pristopov za iskanje izomorfnih podgrafov prikazani na praktičnih primerih. Magistrsko delo združuje teoretične dokaze in algoritme z uporabnimi vpogledi v praktično vrednost metode barvnega označevanja pri reševanju zahtevnih problemov na različnih grafih.20252025-12-10 08:15:06Magistrsko delo/naloga176722VisID: 156783COBISS_ID: 260443139sl