-
Predstavitve grafov z enotsko razdaljo : doktorska disertacijaHorvat, Boris, 1976-Disertacija opisuje probleme povezane z grafi, ki se jih da v evklidski ravnini predstaviti tako, da vozlišča predstavimo s točkami v ravnini povezave pa z daljicami dolžine ena. Probleme preučujemo ... tako z računalniškega (računskega) kot z matematičnega vidika. V uvodnem poglavju povzamemo do sedaj znane rezultate (predvsem matematične) teorije predstavitev grafov z enotsko razdaljo. Ob tem poenotimo terminologijo rezultatov, ki so nastajali v zadnjih petdesetih letih ter jo dopolnemo z dokazi nekaj manjših izrekov. Omenimo tudi prve poskuse generiranja majhnih grafov z enotsko razdaljo z računalnikom in predstavimo rezultate drugih avtorjev. V drugem poglavju obravnavamo najpomembnejše grafovske produkte ▫$k$▫-razsežnih grafov z enotsko razdaljo. V tretjem poglavju ovržemo napačno domnevo, da Heawoodov graf ni graf z enotsko razdaljo. V četrtem poglavju naštejemo vse, tudi degenerirane predstavitve z enotsko razdaljo Petersenovega grafa v ravnini ter obravnavamo relacije med njimi. V petem poglavju opazujemo posplošene Petersenove grafe in ▫$I$▫-grafe. Dokažemo izrek o izomorfizmih ▫$I$▫-grafov in s tem obstoj predstavitve z enotsko razdaljo za veliko večino ▫$I$▫-grafov. Postavimo nekaj domnev, ki jih potrdimo s pomočjo računalnika za vse ▫$I$▫-grafe na največ 2000 vozliščih. V šestem poglavju se ukvarjamo s teorijo izračunljivosti in opazujemo težavnost problema obstoja degenerirane predstavitve grafov z enotsko razdaljo. Dokažemo, da sta odločitveni problem obstoja ▫$k$▫-razsežne degenerirane predstavitve z enotsko razdaljo in odločitveni problem obstoja ▫$k$▫-razsežne degenerirane koordinatizacije z enotsko razdaljo za dani graf NP-polna problema. V zadnjem delu disertacije predstavimo hevristiko za "risanje" grafov z enotsko razdaljo, ki temelji na algoritmu SPE, ki ga je leta 2003 predstavil D. K. Agrafiotis. Definiramo dilacijski koeficient in predstavimo teoretično dobljene meje zanj. Teoretične rezultate primerjamo z rezultati dobljenimi z algoritmom za risanje grafov, ki temelji na simulaciji fizikalnega modela z vzmetmi in z algoritmom, ki s pomočjo lokalne optimizacije minimizira dilacijski koeficient. Sedmo poglavje povzema rezultate objavljene v članku [B. Horvat, T. Pisanski, A. Žitnik: The dilation coefficient of a complete graph, Croat. Chem. Acta, (sprejeto), 2009].Vrsta gradiva - disertacijaZaložništvo in izdelava - Ljubljana : [B. Horvat], 2009Jezik - slovenskiCOBISS.SI-ID - 15190873
Avtor
Horvat, Boris, 1976-
Drugi avtorji
Solina, Franc |
Pisanski, Tomaž
Teme
teorija grafov |
graf z enotsko razdaljo |
predstavitev |
realizacija |
koordinatizacija |
degenerirana predstavitev |
grafovski produkti |
Heawoodov graf |
Petersenov graf |
posplošeni Petersenovi grafi |
▫$I$▫-grafi |
NP poln problem |
dilacijski koeficient |
algoritem |
izomorfizem grafov |
graph theory |
unit-distance graph |
representation |
coordinatization |
degenerate representation |
graph product |
Heawood graph |
Petersen graph |
generalized Petersen graphs |
▫$I$▫-graph |
MP-complete problem |
dilation coefficient |
algorithm |
graph isomorphism
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Horvat, Boris, 1976- | 24421 |
Solina, Franc | 09581 |
Pisanski, Tomaž | 01941 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.