Strategije za preverjanje izomorfnosti grafov

diplomsko delo

Gašper Kreft (Avtor), Tilen Marc (Mentor)

Povzetek

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.

Ključne besede

izomorfizem grafov;barvanje;kanonična forma;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2023
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[G. Kreft]
UDK:	519.174:004(043.2)
COBISS:	167082755
Št. ogledov:	67
Št. prenosov:	14
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Strategies for the graph isomorphism problem
Sekundarni povzetek:	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.
Sekundarne ključne besede:	graph isomorphism;coloring;canonical form;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Barvanje grafov;Računalništvo;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	35 str.
ID:	19921126