20.500.12556/RUL-149981 Strategije za preverjanje izomorfnosti grafov Strategies for the graph isomorphism problem Problem 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. The graph isomorphism problem deals with the question of whether there exists a bijective mapping between any two graphs that preserves the adjacency of their vertices. This is one of the rare known problems for which the question of their classification into the complexity classes P or NP-complete is still open. A heuristic algorithm nauty is presented, which transforms the problem into a search for the canonical form. Through a process of gradually coloring nodes, the algorithm refines the distinction between them, thereby constructing a tree of candidates for the canonical form. Similar ideas are also employed by other practical algorithms. Although they lack a guarantee of a fast performance for all graphs, it turns out that this is the case in most instances. izomorfizem grafov barvanje kanonična forma graph isomorphism coloring canonical form true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2023-09-12 15:35:01 2023-09-12 15:35:11 2023-11-20 10:15:34 0000-00-00 00:00:00 2023 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 36842 167082755 Kreft_Gasper_-_Strategije_za_preverjanje_izomorfnosti_grafov.pdf Kreft_Gasper_-_Strategije_za_preverjanje_izomorfnosti_grafov.pdf 1 F3F7ECEDD5DA5DA3123045008436AD1D f132c34dafb8a212ca9658012c287ad3a6d5907799516aec8d5f254e4f652508 336eadd9-5171-11ee-b4c3-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=174509 Fakulteta za računalništvo in informatiko Fakulteta za matematiko in fiziko 0 0 0