20.500.12556/RUL-187894 Risanje vozliščno tranzitivnih grafov delo diplomskega seminarja Drawing vertex-transitive graphs V delu obravnavamo risanje grafov z visoko stopnjo simetrije, natančneje kubičnih vozliščno tranzitivnih grafov. Klasični algoritmi na osnovi sil, kot sta na primer Eadesov ter Fruchterman–Reingoldov algoritem, pogosto vrnejo zadovoljive slike, vendar simetrije grafa v njih praviloma niso razvidne. Predstavimo prilagoditev Fruchterman–Reingoldovega algoritma, pri kateri poleg grafa podamo tudi njegov avtomorfizem. Vozlišča razporedimo po koncentričnih krožnicah, ki ustrezajo ciklom avtomorfizma, algoritem pa nato optimizira le še polmere in zasuke krožnic, tako da je dobljena slika rotacijsko simetrična glede na podani avtomorfizem. Opišemo tudi metodo, ki za dani graf poišče avtomorfizem, ki po tem postopku vrne čim „lepšo” sliko. Algoritem preizkusimo na grafih iz baze kubičnih vozliščno tranzitivnih grafov in ugotovimo, da najlepše slike tipično dobimo pri avtomorfizmih, ki imajo malo ali nič fiksnih točk in imajo čim daljše cikle. We study the drawing of highly symmetric graphs, more precisely of cubic vertex transitive graphs. Classical force-directed algorithms, such as the Eades algorithm and the Fruchterman–Reingold algorithm, often produce satisfactory pictures, but the symmetries of the graph are usually not visible in them. We present an adaptation of the Fruchterman–Reingold algorithm in which, in addition to the graph, one of its automorphisms is given: the vertices are distributed on concentric circles corresponding to the cycles of the automorphism, and the algorithm then optimizes only the radii and rotations of the circles, so that the resulting drawing is always rotationally symmetric with respect to the given automorphism. We also describe a method which, for a given graph, tries to find an automorphism yielding the „nicest” drawing under this procedure. The algorithm is tested on graphs from the census of cubic vertex-transitive graphs, and we observe that the nicest drawings are typically obtained for automorphisms with few or zero fixed points and long cycles. risanje grafov algoritmi na osnovi sil vozliščno tranzitivni grafi avtomorfizem grafa graph drawing force-directed algorithms vertex-transitive graphs graph automorphism true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2026-09-16 08:15:26 2026-09-16 08:15:29 2026-09-23 15:25:30 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17:004 164157 292242691 24412.pdf 24412.pdf 1 8429DA390959C8BB6F5345A718E5D3CC 41565fbed247d40acdbc6effc26b14fe8302f62789c18fd00398b88eba6b6a87 fb2b4e0f-b195-11f1-8bc5-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=247723 Fakulteta za matematiko in fiziko 0 0 0