Neodvisnostno število grafa

magistrsko delo

Nina Šere (Avtor), Primož Šparl (Mentor)

Povzetek

V magistrskem delu se ukvarjamo s problemom določanja neodvisnostnega števila grafa. S pomočjo prevedbe problema 3-SAT na pripadajoči odločitveni problem o obstoju neodvisnostne množice dane velikosti najprej pokažemo, da ga uvrščamo med tako imenovane NP-polne probleme. Nato se osredotočimo na določanje neodvisnostnega števila za različne grafe. Določimo ga za nekatere dobro znane družine grafov, kot so polni grafi, polni večdelni grafi, cikli, hiperkocke itd. Posvetimo se tudi znani družini posplošenih Petersenovih grafov GP(n,k). Glede na konstrukcijo te družine je jasno, da je zgornja meja neodvisnostnega števila za GP(n,k) največ n, če pa je n liho število, pa celo največ n-1. V magistrskem delu raziskujemo, kakšna je prava vrednost neodvisnostnega števila za različne vrednosti parametra k in s tem ugotavljamo, kako dobra (oziroma slaba) je omenjena zgornja meja.

Ključne besede

neodvisnostna množica;neodvisnostno število;NP - polnost;posplošeni Petersenovi grafi;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2020
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UL PEF - Pedagoška fakulteta
Založnik:	[N. Šere]
UDK:	519.1(043.2)
COBISS:	27336195
Št. ogledov:	311
Št. prenosov:	28
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	The independence number of a graph
Sekundarni povzetek:	In the master's thesis we are dealing with the independence number of a graph. We show, that the well-known problem 3-SAT is reducible to the corresponding decision problem, the so-called independent set problem, which proves that the independent set problem is NP-complete. We then determine the independence number for different graphs, including some very well known infinite families of graphs like complete graphs, multi-partite complete graphs, cycle graphs, hypercube graphs, etc. In the last part of the thesis we focus on the family of generalized Petersen graphs GP(n,k). Based on their construction it is clear, that n is the upper bound for the independence number for GP(n,k). Moreover, if n is odd, the upper bound is n-1. In the master's thesis we determine the exact value of the independence number for different values of parameter k.
Sekundarne ključne besede:	mathematics;matematika;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Ljubljani, Pedagoška fak., Poučevanje, Predmetno poučevanje
Strani:	VII, 65 str.
ID:	12005920