20.500.12556/DKUM-10064 POLNO ZASTRAŽENI GRAFI FULLY GATED GRAPHS 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 pa 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 pa 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 podvojljivosti. Z znanjem o podvojitvi pa pridemo še do druge povezave dvodelnih in polno zastraženih grafov, namreč vsak dvodelni graf je izometrični podgraf nekega polno zastraženega grafa. Iz poljubnega povezanega dvodelnega grafa lahko tudi 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). 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. Razdalja v grafu dvodelni graf konveksna množica grafa zastražena množica Graph distance bipartite graph convex set in graph gated set true true false [P. Pavlič] Slovenski jezik Angleški jezik Diplomsko delo 2009-04-01 08:53:38 2009-04-22 14:14:26 2022-04-11 15:58:08 2022-04-15 03:36:07 2009 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 16810248 URN:SI:UM:DK:UPBTLA37 UNI_Pavlic_Polona_2009.pdf UNI_Pavlic_Polona_2009.pdf 1 5E77952BF87D41987FAB74820C7955D8 b812b1c4eec6579dac1634ed48acbf46a515b39246fca2e2401fba79d37a9d0a b66958df-7c02-11eb-bb7a-00155d0001ca 20.500.12556/dkum/0ebd2227-f537-47c6-9e7f-d99e2927eafe https://dk.um.si/Dokument.php?lang=slv&id=7972 Fakulteta za naravoslovje in matematiko 0 0 0