| Naslov: | POLNO ZASTRAŽENI GRAFI |
|---|
| Avtorji: | ID Pavlič, Polona (Avtor)
ID Klavžar, Sandi (Mentor) Več o mentorju...  |
|---|
| Datoteke: |  UNI_Pavlic_Polona_2009.pdf (663,08 KB)
MD5: 5E77952BF87D41987FAB74820C7955D8
PID: 20.500.12556/dkum/0ebd2227-f537-47c6-9e7f-d99e2927eafe
|
|---|
| Jezik: | Slovenski jezik |
|---|
| Vrsta gradiva: | Diplomsko delo |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | 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). |
|---|
| Ključne besede: | Razdalja v grafu, dvodelni graf, konveksna množica grafa, zastražena množica |
|---|
| Kraj izida: | Maribor |
|---|
| Založnik: | [P. Pavlič] |
|---|
| Leto izida: | 2009 |
|---|
| PID: | 20.500.12556/DKUM-10064 |
|---|
| UDK: | 51(043.2) |
|---|
| COBISS.SI-ID: | 16810248 |
|---|
| NUK URN: | URN:SI:UM:DK:UPBTLA37 |
|---|
| Datum objave v DKUM: | 22.04.2009 |
|---|
| Število ogledov: | 5086 |
|---|
| Število prenosov: | 352 |
|---|
| Metapodatki: |    |
|---|
| Področja: | FNM
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
