Risanje vozliščno tranzitivnih grafovŽerdin, Lenart (Avtor) Vidali, Janoš (Mentor) risanje grafovalgoritmi na osnovi silvozliščno tranzitivni grafiavtomorfizem grafaV 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.20262026-09-16 08:15:26Delo diplomskega seminarja/zaključno seminarsko delo/naloga187894UDK: 519.17:004VisID: 164157COBISS_ID: 292242691sl