Metrična dimenzija grafa

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2011
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[M. Žuželj]
UDC:	51(043.2)
COBISS:	18641160
Views:	2555
Downloads:	170
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	METRIC DIMENSION OF A GRAPH
Secondary abstract:	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.
Secondary keywords:	Metric dimension;distance in graphs;NP-hard problem;path;cycle;complete graph;tree;grid graph;hypercube;Hamming graph.;
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:	50 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19513