| Title: | Geodetsko število medianskih grafov |
|---|
| Authors: | ID Lakner, Sanja (Author)
ID Tepeh, Aleksandra (Mentor) More about this mentor...  |
|---|
| Files: |  UNI_Lakner_Sanja_2011.pdf (2,43 MB)
MD5: 6B6DF110399A94D50E20BE2982292629
PID: 20.500.12556/dkum/e21477d3-bfd1-43d1-9488-61a133612659
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Undergraduate thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | Množico točk S grafa G=(V(G),E(G)) imenujemo geodetska množica v G, če vsako vozlišče grafa G leži na neki najkrajši poti med dvema vozliščema iz množice S. Diplomsko delo preučuje lastnosti minimalnih geodetskih množic v medianskih grafih, ki so definirani kot grafi, v katerih za poljubna tri vozlišča u,v,w∈V(G) presek I(u,v)∩I(u,w)∩I(v,w) sestoji iz natanko enega vozlišča.
Prvo poglavje vsebuje osnovne definicije in opažanja s področja teorije grafov, ki so pomembna za nadaljnje razumevanje. V drugem poglavju so predstavljene osnovne lastnosti medianskih grafov, osredotočili smo se predvsem na dva podrazreda medianskih grafov imenovana kot hiperkocke in drevesa, medianske grafe pa smo karakterizirali s pomočjo periferne ekspanzije. V tretjem poglavju je predstavljeno geodetsko število grafov, v zadnjem pa predstavimo še minimalne geodetske množice v medianskih grafih, preučevane skozi postopek periferne ekspanzije. Karakterizirani so še primeri, ko geodetsko število tudi po postopku periferne ekspanzije ostane enako. Nalogo zaključimo s karakterizacijo medianskih grafov, ki imajo geodetsko število enako 2. |
|---|
| Keywords: | medianski grafi, periferna ekspanzija, zastražene množice, geodetska množica, geodetsko število |
|---|
| Place of publishing: | Maribor |
|---|
| Publisher: | [S. Lakner] |
|---|
| Year of publishing: | 2011 |
|---|
| PID: | 20.500.12556/DKUM-18917 |
|---|
| UDC: | 51(043.2) |
|---|
| COBISS.SI-ID: | 18508040 |
|---|
| NUK URN: | URN:SI:UM:DK:NT54VLD3 |
|---|
| Publication date in DKUM: | 07.07.2011 |
|---|
| Views: | 2946 |
|---|
| Downloads: | 228 |
|---|
| 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. |
