Neprerezne neodvisne množice

magistrsko delo

Matija Kerkoč (Author), Sandi Klavžar (Mentor)

Abstract

V magistrski nalogi obravnavamo neprerezne neodvisne množice. Začeli bomo z definicijo neprereznega neodvisnostnega števila grafa ter njegovimi osnovnimi lastnostmi. Pokažemo povezavo med neprereznimi neodvisnimi množicami ter povezanimi vozliščnimi pokritji v grafu. Glavnina magistrske naloge je posvečena problemu iskanja največjih neprereznih neodvisnih množic (problem MaxNNM). Najprej pokažemo, da je problem rešljiv v polinomskem času za kubične grafe, tetivne grafe ter hiperkocke, nato pa se ukvarjamo z družinami za katere je problem NP-težek. Glavni rezultat je določitev neprereznega neodvisnostnega števila za kartezične produkte dveh ciklov. Ker je problem tesno povezan z računalništvom, bomo v nalogi raziskali algoritme za reševanje problema MaxNNM ter njihovo računsko zahtevnost za različne grafe. Omenili bomo tudi nekatere druge različice problema. Reševanje omenjenega problema porodi bogate aplikacije v vsakdanjem življenju, zato bomo zaključili s pregledom le teh.

Keywords

neprerezne neodvisne množice;povezana vozliščna pokritja;neodvisno število;Z-množice;kartezični produkt grafov;načrtovanje omrežij;

Data

Language:	Slovenian
Year of publishing:	2024
Typology:	2.09 - Master's Thesis
Organization:	UL FMF - Faculty of Mathematics and Physics
Publisher:	[M. Kerkoč]
UDC:	519.1
COBISS:	208188675
Views:	17
Downloads:	13
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Nonseparating independent sets
Secondary abstract:	The topic of the master's thesis are nonseparating independent sets. We start with the definition of the nonseparating independence number of a graph and its basic properties. We show the connection between nonseparating independent sets and connected vertex covers in graphs. The majority of the thesis is dedicated to the problem of finding the largest nonseparating independent sets (the MaxNSIS problem). First, we show that the problem is solvable in polynomial time for cubic graphs, chordal graphs and hypercubes, after that we deal with the graph families for which the problem is NP-hard. Main result is solving the MaxNSIS problem for Cartesian products of two cycles. Since this problem is closely related to computer science, we will explore algorithms for solving the MaxNSIS problem and their computational complexity in various graphs. As solving this problem has rich applications in everyday life, we will conclude with an overview of these applications.
Secondary keywords:	nonseparating independent sets;connected vertex covers;independence number;Z-sets;Cartesian graph product;network construction;
Type (COBISS):	Master's thesis/paper
Study programme:	0
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 2. stopnja
Pages:	X, 58 str.
ID:	25124198