| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 1 / 1
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
KVAZIPRIREJANJA V DVODELNIH GRAFIH
Matej Kren, 2014, magistrsko delo

Opis: V magistrskem delu obravnavamo posplošitve problema iskanja največjega prirejanja v dvodelnem grafu. Dan je dvodelen graf G=(A+B,E) in funkcija potreb, ki vsakemu vozlišču v množici B priredi t.i. potrebo vozlišča. V problemu kvaziprirejanja v dvodelnem grafu G iščemo takšno podmnožico F množice povezav E, da ima vsako vozlišče iz B vsaj toliko F-incidenčnih povezav kot ima potrebo, vozlišča iz množice A pa imajo kar se da uravnoteženo število pripadajočih F-incidenčnih povezav. Problem lahko variiramo tako, da vozliščem iz množice A omejimo število F-incidenčnih povezav s kapacitetno funkcijo in tedaj govorimo o f,g-kvaziprirejanju. V tem primeru nas zanima ali obstaja množica F, ki zadošča kapacitetni funkciji in funkciji potreb v danem dvodelnem grafu. V prvem poglavju so opisani osnovni pojmi in definicije, ki jih potrebujemo v nadaljevanju. V drugem poglavju posplošimo definicijo prirejanja in nekaterih pripadajočih pojmov, ki nam pomagajo dokazati lastnosti kvaziprirejanj. V tretjem poglavju poiščemo učinkovit algoritem za iskanje g-kvaziprirejanja, ki mu dokažemo pravilnost delovanja ter linearno časovno in prostorsko zahtevnost. Algoritem v nadaljevanju dopolnimo tako, da učinkovito poišče optimalno g-kvaziprirejanje ob dodajanju ali odvzemanju vozlišča. V zadnjem poglavju predstavimo odločitveni problem obstoja f,g-kvaziprirejanja. Kot rezultat navedemo široko posplošitev Hallovega poročnega izreka.
Ključne besede: prirejanje, dvodelen graf, kvaziprirejanje, madžarska metoda, Hallov poročni izrek.
Objavljeno: 14.05.2014; Ogledov: 857; Prenosov: 90
.pdf Celotno besedilo (1,03 MB)

Iskanje izvedeno v 0.04 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici