Delne risbe polnih grafovLALOVIĆ, MARKO (Avtor) Fijavž, Gašper (Mentor) delne risbeteorija grafovravninski grafianalitična geometrijaračunalništvoračunalništvo in informatikaračunalništvo in matematikauniverzitetni študijinterdisciplinarni študijdiplomske nalogeDelna risba grafa je risba, kjer povezave grafa predstavimo z daljicami, pri čemer središčnih polovic daljic ne narišemo. Dodatno zahtevamo, da ni križišč med tako narisanimi povezavami. Trenutno najboljša ocena trdi, da ne obstaja delna risba polnega grafa na 241 ali več točkah. V delu to oceno izboljšamo za faktor več kot dva. Pokažemo, da ni možno narisati delne risbe polnega grafa na 102 ali več točkah. Glavni ideji sta dve. Po eni strani uporabljamo drugačno delitev ravnine, na kateri ležijo točke grafa. Namesto koordinatne delitve uporabljamo območja vzdolž poltrakov iz vnaprej izbranih točk risbe. Dobimo delitev, ki ima podobno geometrijo kot delna risba, vendar pa je odvisna od medsebojne lege vnaprej izbranih robnih točk. Po drugi strani pa celotno risbo grafa analiziramo glede na lokacijo treh, deloma celo štirih, točk risbe in ne le dveh kot v prejšnjih ocenah.[M. Lalović]20142014-09-05 14:25:03Diplomsko delo/naloga29436VisID: 14701COBISS_ID: 10785108sl