| Title: | METRIČNA DIMENZIJA GRAFA |
|---|
| Authors: | ID Žuželj, Mateja (Author)
ID Kovše, Matjaž (Mentor) More about this mentor...  |
|---|
| Files: |  UNI_Zuzelj_Mateja_2011.pdf (607,74 KB)
MD5: CFCBD4E1E53ED380938E7E214771AEB4
PID: 20.500.12556/dkum/dc4f89c8-e3a5-4a7d-a73c-99b1cbbc8a13
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Undergraduate thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| 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 š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. |
|---|
| Keywords: | Metrična dimenzija, razdalja v grafih, NP-težek problem, pot, cikel, polni graf, drevo, mreže, hiperkocke, Hammingov graf. |
|---|
| Place of publishing: | Maribor |
|---|
| Publisher: | [M. Žuželj] |
|---|
| Year of publishing: | 2011 |
|---|
| PID: | 20.500.12556/DKUM-20027 |
|---|
| UDC: | 51(043.2) |
|---|
| COBISS.SI-ID: | 18641160 |
|---|
| NUK URN: | URN:SI:UM:DK:ZRBG15YA |
|---|
| Publication date in DKUM: | 27.09.2011 |
|---|
| Views: | 3469 |
|---|
| Downloads: | 221 |
|---|
| Metadata: |    |
|---|
| Categories: | FNM
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
