Kvaziprirejanja v dvodelnih grafih

magistrsko delo

Matej Kren (Avtor), Boštjan Brešar (Mentor)

Povzetek

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;matematika;dvodelni grafi;madžarska metoda;Hallov poročni izrek;magistrska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2014
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[M. Kren]
UDK:	519.172.5(043.2)
COBISS:	20528136
Št. ogledov:	1251
Št. prenosov:	120
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	QUASI-MATCHINGS IN BIPARTITE GRAPHS
Sekundarni povzetek:	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.
Sekundarne ključne besede:	matching;bipartite graph;quasi-matching;Hungarian method;Hall's marriage theorem;master theses;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	XI, 40 f.
ID:	8729278