diplomsko delo
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 |