Distributivna mreža na množici popolnih prirejanj ravninskega dvodelnega grafa

diplomsko delo

Mateja Trbovc Rebernak (Avtor), Petra Žigert Pleteršek (Mentor)

Povzetek

Glavna tema diplomskega dela je, kako priti do distributivne mreže na množici popolnih prirejanj, ravninskega dvodelnega grafa. V drugem poglavju spoznamo osnovne lastnosti grafov. Posebej se poglobimo v dvodelne ravninske grafe. Spomnimo se pojma urejenosti. Izpostavimo pojma delno urejena množica in distributivna mreža. Vse to potrebujemo v nadaljevanju diplomskega dela. Bistvo diplome se začne v tretjem poglavju, kjer definiramo resonančne grafe R(G) in usmerjene resonančne grafe ali digrafe R(G). Za vpeljavo le-teh moramo definirati popolno prirejanje oziroma 1-faktorje ter simetrično razliko med njimi. V četrtem poglavju govorimo o enotski dekompoziciji, kjer podrobneje spoznamo dekompozicijo gozda in ravnine. V predzadnjem poglavju vpeljemo delno urejeno množico kot množico popolnih prirejanj. Za konec sledi rezultat, o tem kako s pomočjo delno urejene množice M(G) in distributivne mreže pridemo do Hassejevega diagrama za končne distributivne mreže. Ta pa je v bijektivnem odnosu z resonančnim digrafom. Torej je distributivna mreža rezultat povezave resonančnih grafov in urejenosti.

Ključne besede

diplomska dela;distributivne mreže;delno urejene množice;popolno prirejanje;Z-transformirani grafi;ravninski dvodelni grafi;Hassejev diagram;povezani grafi;dvodelni grafi;ravninski grafi;drevesa;gozdovi;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2015
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[M. Trbovc Rebernak]
UDK:	519.172.2(043.2)
COBISS:	22109192
Št. ogledov:	1004
Št. prenosov:	89
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	A distributive lattice on the set of perfect matchings of a plane bipartite graph
Sekundarni povzetek:	Main theme of this diploma work is how to get the distributive lattice on the set of perfect matchings of a planar bipartite graph G. In the second chapter we get to know the basic properties of graphs, especially about planar bipartite graphs. We remember the concept of ordered sets, especially about partially ordered ser and distributive lattice. These are all concepts needed through the diploma thesis. The main part of the diplomas is in the third chapter, where we define the resonance graph R(G) and the directed resonance graph or digraph. For the introduction of these we need to define the set of perfect matchings M(G) t.i. 1-factors of G and the symmetric difference between them. In the fourth chapter we talk about the unit decomposition and further about the decomposition of a forest in a plane. In the penultimate chapter we introduce the set of perfect matching M(G) as a partially ordered set and introduce its Hasse diagram which is in a bijective relationship with the resonance digraph. So distributive lattice on M(G) is a result of the connection between the resonance graphs and order sets.
Sekundarne ključne besede:	theses;distributive lattices;partially ordered sets;posets;forest posets;perfect matching;Z-transformation graphs;planar bipartite graphs;Hasse diagram;connected graphs;bipartite graphs;planar graphs;trees;forests;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	66 f.
ID:	8756658