| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava
Prva stran > Izpis gradiva

Izpis gradiva Pomoč

Naslov:KVAZIPRIREJANJA V DVODELNIH GRAFIH
Avtorji:ID Kren, Matej (Avtor)
ID Brešar, Boštjan (Mentor) Več o mentorju... Novo okno
Datoteke:.pdf MAG_Kren_Matej_2014.pdf (1,03 MB)
MD5: AB2C8976A287231A023CBD39F603C22E
 
Jezik:Slovenski jezik
Vrsta gradiva:Magistrsko delo/naloga
Tipologija:2.09 - Magistrsko delo
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
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.
Kraj izida:Maribor
Založnik:[M. Kren]
Leto izida:2014
PID:20.500.12556/DKUM-44100 Novo okno
UDK:519.172.5(043.2)
COBISS.SI-ID:20528136 Novo okno
NUK URN:URN:SI:UM:DK:GL7XTFWN
Datum objave v DKUM:14.05.2014
Število ogledov:1820
Število prenosov:161
Metapodatki:XML DC-XML DC-RDF
Področja:FNM
:
KREN, Matej, 2014, KVAZIPRIREJANJA V DVODELNIH GRAFIH [na spletu]. Magistrsko delo. Maribor : M. Kren. [Dostopano 18 april 2025]. Pridobljeno s: https://dk.um.si/IzpisGradiva.php?lang=slv&id=44100
Kopiraj citat
  
Skupna ocena:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:Bookmark and Share


Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Sekundarni jezik

Jezik:Angleški jezik
Naslov:QUASI-MATCHINGS IN BIPARTITE GRAPHS
Opis:In master thesis we discuss generalizations of the problem of determining maximum matching in bipartite graphs. A bipartite graph G=(A+B,E), and a need function that assigns the so-called need of every vertex in B, are given. In the quasi-matching problem in a bipartite graph G we seek a subset of edges F, where every vertex from B has at least as many F-incident edges as its need, and vertices in A have the number of F-incident edges as balanced as possible. We can vary the problem by limiting the number of F-incident edges with a capacity function to vertices from A, and we talk about f,g-quasi-matching. In that case we are interested in, whether a set F that fulfils the capacity and need function in the bipartite graph, actually exists. The first chapter introduces basic concepts and definitions that are needed for further understanding of the thesis. In the second chapter we generalize the definition of matching and some concepts that help us to prove some quasi-matching properties. In third chapter we present an efficient algorithm for finding g-quasi-matching in a bipartite graph, for which we prove correctness and linear time and space complexity. In the last part of the chapter we improve the algorithm so that it efficiently finds g-quasi-matching if a vertex is added or taken. In the last chapter we present decision problem of existence of f,g-quasi-matching. As a result generalization of Hall's marriage theorem is given.
Ključne besede:matching, bipartite graph, quasi-matching, Hungarian method, Hall's marriage theorem


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

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

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici