| Naslov: | Aplikacije teorije grafov v komunikacijskih omrežjih |
|---|
| Avtorji: | ID Čevnik, Maja (Avtor)
ID Žerovnik, Janez (Mentor) Več o mentorju...  |
|---|
| Datoteke: |  EDOK_Cevnik_Maja_2015.pdf (567,00 KB)
MD5: D6605B3A302CB22FBFBEBB5529CF1FC5
|
|---|
| Jezik: | Slovenski jezik |
|---|
| Vrsta gradiva: | Doktorska disertacija |
|---|
| Tipologija: | 2.08 - Doktorska disertacija |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | Dobra komunikacija med enotami omrežja ali med procesorji je bistvenega pomena za dobro delovanje. Veliko problemov povezanih s komunikacijskimi omrežji ali paralelno arhitekturo lahko prenesemo v probleme teorije grafov. Ker je dosti izmed teh problemov NP-težkih, se v tem primeru osredotočamo na reševanje podproblemov, ki jih znamo rešiti v polinomskem času. Eden izmed osnovnih problemov usmerjanja informacij v komunikacijskih omrežjih je problem enovozliščnega razširjanja. To je proces razširjanja informacije iz enega (izvornega) vozlišča do vseh ostalih vozlišč grafa z zaporedjem klicev med sosednjimi vozlišči, pri čemer je potrebno upoštevati pravila enovozliščnega razširjanja. V disertaciji se bomo omejili na problem enovozliščnega razširjanja v $k$-omejenih kaktus grafih, kjer bomo podali algoritem, ki reši problem razširjanja iz izvornega vozlišča v času $O(n log n)$.
Podali bomo tudi algoritem, ki s pomočjo rezultatov dobljenih ob računanju časa razširjanja izvornega vozlišča, izračuna čas razširjanja vseh vozlišč grafa s časovno zahtevnostjo $O(n log n)$. Kot stranski produkt bomo podali še shemo razširjanja vseh vozlišč v $k$-omejenem kaktusu in center razširjanja $k$-omejenega kaktus grafa.
noindent V drugem delu bomo proučevali Wienerjevo število za usmerjene grafe in omenili povezavo z načrtovanjem optičnih omrežij. Izkaže se, da so usmerjeni grafi z ekstremnim modificiranim Wienerjevim številom optimalna omrežja. Proučevali bomo usmerjene grafe z najmanjšo vrednostjo za eno izmed možnih posplošitev Wienerjevega števila za usmerjene grafe. Za digrafe z lastnostjo enolične najkrajše poti bomo podali minimalne digrafe za $alpha<0$ in $alpha>1$, podali bomo tudi nekaj delnih rezultatov za primer, ko je $0<alpha <0.$ |
|---|
| Ključne besede: | enovozliščno razširjanje, kaktus graf, čas razširjanja, shema razširjanja, center razširjanja, Wienerjevo število, usmerjen graf, komunikacijska omrežja, usmerjena komunikacijska omrežja |
|---|
| Kraj izida: | [Maribor |
|---|
| Založnik: | M. Čevnik] |
|---|
| Leto izida: | 2015 |
|---|
| PID: | 20.500.12556/DKUM-47232 |
|---|
| UDK: | 519.17:004.7(043.3) |
|---|
| COBISS.SI-ID: | 21305608 |
|---|
| NUK URN: | URN:SI:UM:DK:2LSLKXV7 |
|---|
| Datum objave v DKUM: | 13.04.2015 |
|---|
| Število ogledov: | 1916 |
|---|
| Število prenosov: | 150 |
|---|
| 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. |
