Metrična dimenzija grafa

diplomsko delo

Mateja Žuželj (Avtor), Matjaž Kovše (Mentor)

Povzetek

V prvem poglavju diplomskega dela predstavimo osnovne pojme iz teorije grafov, podamo definicije in preproste primere grafov. V drugem poglavju definiramo metrično dimenzijo grafa. V tretjem poglavju se posvetimo grafom z majhno metrično dimenzijo. Poti so edini grafi z metrično dimenzijo ena. Ogledamo si lastnosti, ki so značilne za grafe z metrično dimenzijo dva. Ob koncu tega poglavja se seznanimo z metrično dimenzijo ciklov, ki so predstavniki grafov z metrično dimenzijo dva. V četrtem poglavju obravnavamo metrično dimenzijo različnih primerov grafov. Najprej spoznamo metrično dimenzijo polnih grafov, nato dreves in na koncu mrež, pri katerih kot poseben primer pogledamo hiperkocke. Za drevesa podamo tudi enostaven algoritem za postavitev baznih vozlišč. V zadnjem poglavju se ukvarjamo z uporabo metrične dimenzije. Podamo primere uporabe metrične dimenzije v miselnih problemih in igrah, navigaciji, računalništvu in kemiji.

Ključne besede

matematika;grafi;metrična dimenzija;razdalja;pot;cikel;polni graf;drevesa;mreže;hiperkocke;diplomska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2011
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[M. Žuželj]
UDK:	51(043.2)
COBISS:	18641160
Št. ogledov:	2555
Št. prenosov:	170
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	METRIC DIMENSION OF A GRAPH
Sekundarni povzetek:	In first chapter of this thesis we present the basic concepts from theory of graphs, we give definitions and simple examples of graphs. In second chapter we define metric dimension of a graph. In third chapter we focus on graphs with small metric dimension. Paths are the only graphs with metric dimension one. We take a closer look at properties, typical for graphs with metric dimension two. At the end of this chapter we get to know metric dimension of cycles, which represent graphs with metric dimension two. In fourth chapter we look at metric dimension of different examples of graphs. At first we learn metric dimension of complete graphs, than trees and in the end grid graph where we deal with a special example of hypercubes. For trees we give a simple algorithm for setting up vertices from a basis. In the last chapter we deal with applications of metric dimension. We give examples how to use metric dimension in mind games, combinatorial games, navigation, computer science and in chemistry.
Sekundarne ključne besede:	Metric dimension;distance in graphs;NP-hard problem;path;cycle;complete graph;tree;grid graph;hypercube;Hamming graph.;
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:	50 f.
Ključne besede (UDK):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19513