| Title: | POLNO ZASTRAŽENI GRAFI |
|---|
| Authors: | ID Pavlič, Polona (Author)
ID Klavžar, Sandi (Mentor) More about this mentor...  |
|---|
| Files: |  UNI_Pavlic_Polona_2009.pdf (663,08 KB)
MD5: 5E77952BF87D41987FAB74820C7955D8
PID: 20.500.12556/dkum/0ebd2227-f537-47c6-9e7f-d99e2927eafe
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Undergraduate thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | Množica X v grafu G je zastražena, če za vsako vozlišče iz GX v X obstaja enolično določeno vozlišče, preko katerega so razdalje do vozlišč iz X najkrajše. Diplomsko delo preučuje grafe, v katerih je vsaka konveksna množica grafa zastražena - polno zastražene grafe. Prva opazka glede teh grafov je, da morajo biti nujno dvodelni. S preprostim algoritmom, ki deluje v polinomskem času, lahko za poljuben (dvodelni) graf preverimo, ali je polno zastražen ali ne. Algoritem, ki temelji na zoženju preverjanja vseh konveksnih množic le na tiste, ki so konveksne lupine parov vozlišč, je predstavljen v 3. poglavju. Do prvih pravih primerov polno zastraženih grafov nas pripeljejo hiperkocke. Z nekaj ozadja iz teorije grafov lahko dokažemo tudi, da so medianski grafi natanko polno zastražene delne kocke. Iz znanih polno zastraženih grafov pa lahko nadalje s pomočjo nekaterih operacij nad grafi konstruiramo nove take. Hitro vidimo, da kartezični produkt ohranja polno zastraženost, prav tako je s konveksno amalgamacijo grafov. Iz danih polno zastraženih grafov prav take tvori tudi posplošena konveksna ekspanzija, nekaj več preglavic pa povzroča konveksna podvojitev, kjer so potrebne dodatne predpostavke. Polna zastraženost se ohranja le če konveksna množica, ki jo podvajamo, zadošča dodatnim predpostavkam podvojljivosti. Z znanjem o podvojitvi pa pridemo še do druge povezave dvodelnih in polno zastraženih grafov, namreč vsak dvodelni graf je izometrični podgraf nekega polno zastraženega grafa. Iz poljubnega povezanega dvodelnega grafa lahko tudi hitro, brez zgornjih operacij, dobimo polno zastražen graf - v vsako množico razbitja dodamo vozlišče, ki je sosednje z vsemi vozlišči iz druge množice razbitja (dvodelni dominator). |
|---|
| Keywords: | Razdalja v grafu, dvodelni graf, konveksna množica grafa, zastražena množica |
|---|
| Place of publishing: | Maribor |
|---|
| Publisher: | [P. Pavlič] |
|---|
| Year of publishing: | 2009 |
|---|
| PID: | 20.500.12556/DKUM-10064 |
|---|
| UDC: | 51(043.2) |
|---|
| COBISS.SI-ID: | 16810248 |
|---|
| NUK URN: | URN:SI:UM:DK:UPBTLA37 |
|---|
| Publication date in DKUM: | 22.04.2009 |
|---|
| Views: | 5089 |
|---|
| Downloads: | 352 |
|---|
| 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. |
