Strategije za preverjanje izomorfnosti grafov

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2023
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[G. Kreft]
UDC:	519.174:004(043.2)
COBISS:	167082755
Views:	67
Downloads:	14
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Strategies for the graph isomorphism problem
Secondary abstract:	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.
Secondary keywords:	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;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	35 str.
ID:	19921126