[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
English
Logo            
  Logo Prijava | Registracija
 
 

Problem Steinerjevega drevesa

Darja Prevc Mavrin (2017) Problem Steinerjevega drevesa. Magistrsko delo.

[img] PDF
Download (1421Kb)

    Povzetek

    S problemom Steinerjevega drevesa se je ukvarjalo veliko število matematikov. Steinerjevo drevo je poimenovano po švicarskem matematiku Jakobu Steinerju (1796-1863), čeprav ni jasno, kakšen je bil sploh njegov prispevek k temu problemu. Problem Steinerjevega drevesa je iskanje najkrajše mreže s fiksnim številom točk v ravnini (osredotočili se bomo na evklidsko), pri čemer lahko dodajamo točke, ki omogočajo minimizacijo celotne dolžine drevesa. Te točke imenujemo Steinerjeve točke. Razmerje med dolžino Steinerjevega drevesa in dolžino minimalnega vpetega drevesa predstavlja Steinerjevo razmerje. V magistrskem delu bomo predstavili lastnosti Steinerjevega drevesa in točne ter aproksimativne algoritme, ki se uporabljajo za reševanje problema Steinerjevega drevesa. Obdelali bomo primere Steinerjevega drevesa za tri oziroma štiri terminale, ki so odvisni od postavitve terminalov v ravnini. Problem Steinerjevega drevesa ni uporaben le v matematičnem smislu, ampak tudi v realnem življenju (na primer v prometni infrastrukturi).

    Tip vnosa: Delo ali doktorska disertacija (Magistrsko delo)
    Ključne besede: evklidska ravnina, Steinerjevo drevo, Steinerjeva točka, minimalno vpeto drevo, Steinerjevo razmerje, lastnosti Steinerjevega drevesa, točni algoritem, aproksimativni algoritem
    Število strani: 62
    Jezik vsebine: Slovenščina
    Mentor / Somentorji:
    Mentor / SomentorjiIDFunkcija
    prof. dr. Matija CenceljMentor
    dr. Boštjan GabrovšekSomentor
    Povezava na COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=11655241)
    Ustanova: Univerza v Ljubljani
    Fakulteta: Pedagoška fakulteta
    ID vnosa: 4587
    Datum vnosa: 18 Jul 2017 12:41
    Zadnja sprememba: 18 Jul 2017 12:41
    URI: http://pefprints.pef.uni-lj.si/id/eprint/4587

    Akcije (potrebna je prijava)

    Pregled vnosa