Strategije za preverjanje izomorfnosti grafovKreft, Gašper (Avtor) Marc, Tilen (Mentor) izomorfizem grafovbarvanjekanonična formaProblem izomorfizma grafov se ukvarja z vprašanjem, kdaj med poljubnima grafoma obstaja bijektivna preslikava, ki ohranja sosednost vozlišč. Gre za enega redkih znanih problemov, za katerega se ne ve, ali spada v kateregakoli izmed razredov P ali NP-poln. Predstavljen je hevrističen algoritem nauty, ki problem prevede na iskanje kanonične forme. S postopnim barvanjem vozlišč algoritem izpopolnjuje razlikovanje med temi vozlišči in tako gradi drevo kandidatov za kanonično formo. Podobne ideje uporabljajo tudi ostali praktični algoritmi. Čeprav nimajo zagotovila, da za vse grafe delujejo v polinomskem času, se izkaže, da je v večini primerov vendarle tako.20232023-09-12 15:35:01Diplomsko delo/naloga149981VisID: 36842COBISS_ID: 167082755sl