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

Največja prirejanja v grafih

Vanja Okorn (2012) Največja prirejanja v grafih. Diplomsko delo.

[img]
Predogled
PDF
Download (1077Kb)

    Povzetek

    V diplomskem delu se osredotočimo na eno izmed pomembnejših področij v kombinatorični optimizaciji, ki obravnava problem največjega prirejanja v grafih. Prirejanja v grafu so podmnožice množice povezav danega grafa, za katere velja, da nimajo skupnega krajišča. Prirejanje je največje, če ne obstaja prirejanje, ki vsebuje več povezav. V diplomskem delu predstavimo osnovne pojme in rezultate v zvezi s problemom največjega prirejanja v grafih. Obravnavamo tudi vprašanje kdaj ima graf tako imenovano popolno prirejanje. V prvem delu se lotimo iskanja največjega prirejanja v dvodelnih grafih. Pri tem si pomagamo s prevedbo našega problema na problem maksimalnega pretoka v ustreznem omrežju. Nato predstavimo znani algoritem za reševanje slednjega problema in pokažemo, kako lahko na ta način poiščemo največje prirejanje v dvodelnem grafu. V drugem delu obravnavamo problem iskanja največjega prirejanja v splošnih grafih. Tu si pogledamo pogoje, ki nam zagotavljajo, da ima poljuben graf popolno prirejanje. Na koncu pa se seznanimo z nekaj problemi iz vsakdanjega življenja, ki jih lahko prevedemo na probleme iskanja največjega prirejanja v grafih.

    Tip vnosa: Delo ali doktorska disertacija (Diplomsko delo)
    Ključne besede: največje prirejanje, popolno prirejanje, pretoki
    Število strani: 70
    Jezik vsebine: Slovenščina
    Mentor / Somentorji:
    Mentor / SomentorjiIDFunkcija
    doc. dr. Primož ŠparlMentor
    Povezava na COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=9321289)
    Ustanova: Univerza v Ljubljani
    Fakulteta: Pedagoška fakulteta
    ID vnosa: 906
    Datum vnosa: 19 Jul 2012 12:22
    Zadnja sprememba: 19 Jul 2012 12:22
    URI: http://pefprints.pef.uni-lj.si/id/eprint/906

    Akcije (potrebna je prijava)

    Pregled vnosa