Polno zastraženi grafi

diplomsko delo

Polona Pavlič (Avtor), Sandi Klavžar (Mentor)

Povzetek

Množica X v grafu G je zastražena, če za vsako vozlišče iz GX v X obstaja enolično določeno vozlišče, preko katerega so razdalje do vozlišč iz X najkrajše. Diplomsko delo preučuje grafe, v katerih je vsaka konveksna množica grafa zastražena - polno zastražene grafe. Prva opazka glede teh grafov je, da morajo biti nujno dvodelni. S preprostim algoritmom, ki deluje v polinomskem času, lahko za poljuben (dvodelni) graf preverimo, ali je polno zastražen ali ne. Algoritem, ki temelji na zoženju preverjanja vseh konveksnih množic le na tiste, ki so konveksne lupine parov vozlišč, je predstavljen v 3. poglavju. Do prvih pravih primerov polno zastraženih grafov nas pripeljejo hiperkocke. Z nekaj ozadja iz teorije grafov lahko dokažemo tudi, da so medianski grafi natanko polno zastražene delne kocke. Iz znanih polno zastraženih grafov lahko nadalje s pomočjo nekaterih operacij nad grafi konstruiramo nove take. Hitro vidimo, da kartezični produkt ohranja polno zastraženost, prav tako je s konveksno amalgamacijo grafov. Iz danih polno zastraženih grafov prav take tvori tudi posplošena konveksna ekspanzija, nekaj več preglavic povzroča konveksna podvojitev, kjer so potrebne dodatne predpostavke. Polna zastraženost se ohranja le, če konveksna množica, ki jo podvajamo, zadošča dodatnim predpostavkam pod vojljivosti. Z znanjem o podvojitvi pridemo do druge povezave dvodelnih in polno zastraženih grafov, namreč vsak dvodelni graf je izometrični pod graf nekega polno zastraženega grafa. Iz poljubnega povezanega dvodelnega grafa lahko hitro, brez zgornjih operacij, dobimo polno zastražen graf - v vsako množico razbitja dodamo vozlišče, ki je sosednje z vsemi vozlišči iz druge množice razbitja (dvodelni dominator).

Ključne besede

matematika;grafi;razdalje;dvodelni grafi;konveksne množice;zastražene množice;diplomska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2009
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[P. Pavlič]
UDK:	51(043.2)
COBISS:	16810248
Št. ogledov:	3817
Št. prenosov:	306
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	FULLY GATED GRAPHS
Sekundarni povzetek:	A set of vertices X in a graph G is gated, if, for every vertex in GX there exists a unique vertex in X, such that distances to vertices in X are shortest via this vertex. Graduation thesis investigates graphs whose every convex set is gated - fully gated graphs. Firstly we see that every fully gated graph has to be bipartite. A polynomial algorithm lets us check for any (bipartite) graph whether it is fully gated or not. This algoritm is based on the restriction of all convex sets, which need to be investigated, to only those which are convex hulls of pairs of vertices. It is presented in Section 3. First fully gated graphs that we find are hypercubes. With some knowledge from graph theory we also find out that median graphs are the fully gated partial cubes. We can form new fully gated graphs with some operations on graphs. The Cartesian product of fully gated graphs forms fully gated graphs. So does convex identification. If we generalize convex expansion, it is also closed under fully gated graphs. More trouble occurs in convex duplication. If we perform convex duplicaton of a fully gated graph along a duplicable convex set in a graph, it remains fully gated. Every bipartite graph is an isometric subgraph of a fully gated graph. Whenever we have a bipartite graph and we add a vertex called bipartite dominator on both sets of a bipartition, we always get a fully gated graph.
Sekundarne ključne besede:	Graph distance;bipartite graph;convex set in graph;gated set;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	45 f.
Ključne besede (UDK):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	17719