Toroidni grafiMaček, Manja (Avtor) Šparl, Primož (Mentor) ravninska vložitev2-celična vložitevtoroidni grafminimalni nevložljivi grafEulerjeva formulagrafične metodeTo magistrsko delo sodi na področje teorije grafov, ki se med drugim ukvarja z vložitvami grafov na različne ploskve. Najenostavnejša je obravnava ravninskih vložitev, kjer gre za upodobitev grafov v ravnino, za katere postavimo zahtevo, da se povezave grafa med seboj ne smejo sekati. V primeru, da imamo ravninsko vložitev nekega povezanega grafa, lahko zanjo podamo Eulerjevo formulo, ki povezuje število vozlišč, povezav in lic te upodobitve. Prav tako je znan izrek Kuratowskega, ki podaja potreben in zadosten pogoj za obstoj ravninske vložitve danega grafa. Ta izrek nam pove, da na ravnini obstajata le dva tako imenovana minimalna nevložljiva grafa, v smislu, da dani graf ni ravninski natanko tedaj, ko na nek način (ki ga na tem mestu še ne bomo navajali) vsebuje vsaj enega od teh dveh grafov. V tem magistrskem delu pa se osredotočimo na analizo vložitev grafov na torus. čeprav je torus kot tak relativno enostavna ploskev, moramo biti pri podajanju definicij glede vložitev na torus previdnejši kot na ravnini. V magistrskem delu predstavimo zahteve 2-celične vložitve na torus in pojasnimo, zakaj moramo biti pri njeni definiciji tako natančni. Prav tako preverimo, kakšna je Eulerjeva formula za 2-celične vložitve na torus. Videli bomo, da na torusu zaenkrat ne moremo podati analogije izreka Kuratowskega, saj še ne vemo, koliko je vseh minimalnih nevložljivih grafov na torusu. Kljub temu predstavimo nekaj teh grafov in pokažemo, zakaj jih tako imenujemo. V zadnjem delu nas bo zanimalo, ali lahko kakšne ravninske grafe vložimo tudi na torus, katere neravninske grafe lahko vložimo na torus in kateri so grafi, ki na torus niso vložljivi.M. Maček20252025-03-06 08:30:08Magistrsko delo/naloga167679UDK: 51(043.2)VisID: 183153COBISS_ID: 228261635sl