20.500.12556/DKUM-20027 METRIČNA DIMENZIJA GRAFA METRIC DIMENSION OF A GRAPH 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 še 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 še 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. 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. Metrična dimenzija razdalja v grafih NP-težek problem pot cikel polni graf drevo mreže hiperkocke Hammingov graf. Metric dimension distance in graphs NP-hard problem path cycle complete graph tree grid graph hypercube Hamming graph. true true false [M. Žuželj] Slovenski jezik Angleški jezik Diplomsko delo 2011-09-06 20:01:20 2011-09-27 10:25:04 2022-04-13 15:50:27 2023-12-26 03:29:37 2011 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 18641160 URN:SI:UM:DK:ZRBG15YA UNI_Zuzelj_Mateja_2011.pdf UNI_Zuzelj_Mateja_2011.pdf 1 CFCBD4E1E53ED380938E7E214771AEB4 da8ac9eece9efce53e51867f28420092409cc8065bb42bfc16e952cd67924d6f 849a827b-7c05-11eb-bb7a-00155d0001ca 20.500.12556/dkum/dc4f89c8-e3a5-4a7d-a73c-99b1cbbc8a13 https://dk.um.si/Dokument.php?lang=slv&id=24547 Fakulteta za naravoslovje in matematiko 0 0 0