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

diplomsko delo

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

Abstract

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.

Keywords

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;

Data

Language:	Slovenian
Year of publishing:	2015
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[M. Trbovc Rebernak]
UDC:	519.172.2(043.2)
COBISS:	22109192
Views:	1004
Downloads:	89
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	A distributive lattice on the set of perfect matchings of a plane bipartite graph
Secondary abstract:	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.
Secondary keywords:	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:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	66 f.
ID:	8756658