-
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].Type of material - dissertationPublication and manufacture - Ljubljana : [B. Horvat], 2009Language - slovenianCOBISS.SI-ID - 15190873
Author
Horvat, Boris, 1976-
Other authors
Solina, Franc |
Pisanski, Tomaž
Topics
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
Library | Call number – location, accession no. ... | Copy status |
---|---|---|
National and University Library, Ljubljana | GS II 706267 glavno skladišče | available - reading room |
Library FKKT and FRI, Ljubljana | FRIdr 623 IN: 200056722 |
available - reading room |
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Horvat, Boris, 1976- | 24421 |
Solina, Franc | 09581 |
Pisanski, Tomaž | 01941 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.