Polno zastraženi grafi

diplomsko delo

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

Abstract

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).

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2009
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[P. Pavlič]
UDC:	51(043.2)
COBISS:	16810248
Views:	3817
Downloads:	306
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	FULLY GATED GRAPHS
Secondary abstract:	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.
Secondary keywords:	Graph distance;bipartite graph;convex set in graph;gated set;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	45 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	17719