Strategije za preverjanje izomorfnosti grafov

Kreft, Gašper (avtor), Marc, Tilen (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: izomorfizem grafov, barvanje, kanonična forma
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko; FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2023
• PID: 20.500.12556/RUL-149981
• COBISS.SI-ID: 167082755
• Datum objave v RUL: 12.09.2023

KREFT, Gašper, 2023, Strategije za preverjanje izomorfnosti grafov [na spletu]. Diplomsko delo. [Dostopano 19 maj 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=149981

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Strategies for the graph isomorphism problem

Izvleček

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.

• Ključne besede: graph isomorphism, coloring, canonical form