20.500.12556/RUL-158157 Predstavitve grafov z enotsko razdaljo doktorska disertacija Representations of unit-distance graphs 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]. The doctoral thesis describes problems concerning graphs that can be represented in the Euclidean plane (or ▫$k$▫-space) in such a way, that vertices are represented as points in the plane (▫$k$▫-space) and edges as line segments of unit lengths. Problems are observed from a computational and a mathematical point of view. In the first part of the thesis the (already known, mainly mathematical) theory of unit-distance graph representations is presented; at the same time the terminology of the results is unified and several propositions are proved. First computer aided attempts to generate small graphs with a unit-distance representation are discussed. In the following chapter the well-known graph products of ▫$k$▫-dimensional unit-distance graphs are studied. The third chapter disproves the wrong assumption that Heawood graph is not a unit-distance graph, by providing the unit-distance coordinatization of it. In the fourth chapter all degenerate unit-distance representations of the Petersen graph in the Euclidean plane are presented and some relationships among them are observed. In the following chapter generalized Petersen graphs and ▫$I$▫-graphs are observed. Necessary and sufficient conditions for two ▫$I$▫-graphs to be isomorphic are given. As a corollary it is shown that a large subclass of ▫$I$▫-graphs can be drawn with unit-distances in the Euclidean plane by using the representation with a rotational symmetry. Conjectures concerning unit-distance coordinatizations and highly-degenerate unit-distance representations of ▫$I$▫-graphs are stated and verified for all ▫$I$▫-graphs up to 2000 vertices. In the sixth chapter the decision problems that ask about the existence of a degenerate ▫$k$▫-dimensional unit-distance representation or coordinatization of a given graph are shown to be NP-complete. In the last chapter of the thesis a heuristics that draws a given graph in the Euclidean plane by minimizing the quotient of the longest and the shortest edge length is presented; see SPE algorithm in [D.Agrafiotis. Stochastic proximity embedding. J. Comput. Chem., 24 (2003) 1215-122]. The dilation coefficient of a graph is introduced and theoretically obtained bounds for the dilation coefficient of a complete graph are given. The calculated upper bounds for the dilation coefficients of complete graphs are compared to the values obtained by three graph-drawing algorithms, see [B. Horvat, T. Pisanski, A. Žitnik: The dilation coefficient of a complete graph, Croat. Chem. Acta, (accepted), 2009]. 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 true false false B. Horvat Slovenski jezik Slovenski jezik Doktorska disertacija 2024-05-27 09:46:19 2024-05-27 09:46:26 2024-06-21 03:43:15 0000-00-00 00:00:00 2009 0 Ljubljana 2009 Ljubljana 154 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.3) 15190873 horvat_boris.disertacija.pdf horvat_boris.disertacija.pdf 1 CD8043E3FDA6532FB85D1FAD2A0CEDDD e713ffecfb4c5a78602e29730d72840b185e466d8830df450715f2d0147e15e7 3941cbc9-1bfd-11ef-927e-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=185627 Fakulteta za računalništvo in informatiko 0 0 0