izpis_h1_title_alt

Delne risbe polnih grafov : diplomsko delo
Lalović, Marko (Avtor), Fijavž, Gašper (Mentor) Več o mentorju... Povezava se odpre v novem oknu

URLURL - Predstavitvena datoteka, za dostop obiščite http://eprints.fri.uni-lj.si/2630/ Povezava se odpre v novem oknu

Izvleček
Delna 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.

Jezik:Slovenski jezik
Ključne besede:delne risbe, teorija grafov, ravninski grafi, analitična geometrija, računalništvo, računalništvo in informatika, računalništvo in matematika, univerzitetni študij, interdisciplinarni študij, diplomske naloge
Vrsta gradiva:Diplomsko delo/naloga (mb11)
Tipologija:2.11 - Diplomsko delo
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2014
Založnik:[M. Lalović]
Št. strani:74 str.
UDK:004(043.2)
COBISS.SI-ID:10785108 Povezava se odpre v novem oknu
Število ogledov:462
Število prenosov:72
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Partial edge drawings of complete graphs
Izvleček:
Partial edge drawing of a graph is a rectilinear drawing in which a middle portion of an edge is removed from the drawing. In addition, we require that the drawing is without edge crossings. Currently, the best estimate claims that there is no partial edge drawing of the complete graph on 241 or more points. In this work we improve the estimate by a factor of more than two. We show that it is not possible to draw a partial edge drawing of the complete graph on 102 or more points. The main ideas are two. On the one hand, we use a different division of the plane on which the points of the graph are located. Instead of coordinate division of the plane, we use the areas along the rays from pre-selected points of the drawing. On the other hand, we analyze the whole drawing of the graph by the location of three, sometimes even four, points of the drawing and not only two points as in the previous estimates.

Ključne besede:partial edge drawings, graph theory, planar graphs, analytic geometry, computer science, computer and information science, computer science and mathematics, interdisciplinary studies, diploma

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj