Vaš brskalnik ne omogoča JavaScript!
JavaScript je nujen za pravilno delovanje teh spletnih strani. Omogočite JavaScript ali pa uporabite sodobnejši brskalnik.
Repozitorij Univerze v Ljubljani
Nacionalni portal odprte znanosti
Odprta znanost
DiKUL
slv
|
eng
Iskanje
Brskanje
Novo v RUL
Kaj je RUL
V številkah
Pomoč
Prijava
Podrobno
Neprerezne neodvisne množice : magistrsko delo
ID
Kerkoč, Matija
(
Avtor
),
ID
Klavžar, Sandi
(
Mentor
)
Več o mentorju...
PDF - Predstavitvena datoteka,
prenos
(695,05 KB)
MD5: EF1139EB653D4F0216722E77A46D043F
Galerija slik
Izvleček
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.
Jezik:
Slovenski jezik
Ključne besede:
neprerezne neodvisne množice
,
povezana vozliščna pokritja
,
neodvisnostno število
,
Z
-množice
,
kartezični produkt grafov
,
načrtovanje omrežij
Vrsta gradiva:
Magistrsko delo/naloga
Tipologija:
2.09 - Magistrsko delo
Organizacija:
FMF - Fakulteta za matematiko in fiziko
Leto izida:
2024
PID:
20.500.12556/RUL-162403
UDK:
519.17
COBISS.SI-ID:
208188675
Datum objave v RUL:
22.09.2024
Število ogledov:
390
Število prenosov:
66
Metapodatki:
Citiraj gradivo
Navadno besedilo
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
KERKOČ, Matija, 2024,
Neprerezne neodvisne množice : magistrsko delo
[na spletu]. Magistrsko delo. [Dostopano 8 julij 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=162403
Kopiraj citat
Objavi na:
Sekundarni jezik
Jezik:
Angleški jezik
Naslov:
Nonseparating independent sets
Izvleček:
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.
Ključne besede:
nonseparating independent sets
,
connected vertex covers
,
independence number
,
Z
-sets
,
Cartesian graph product
,
network construction
Podobna dela
Podobna dela v RUL:
Iščem podobna dela...
Podobna dela v drugih slovenskih zbirkah:
Nazaj