20.500.12556/DKUM-48277 Distributivna mreža na množici popolnih prirejanj ravninskega dvodelnega grafa A distributive lattice on the set of perfect matchings of a plane bipartite graph 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 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. distributivna mreža delno urejena množica popolno prirejanje Z-transformirani graf ravninski dvodelen graf Hassejev diagram povezani graf dvodelni graf ravninski graf drevo gozd distributive lattice partially ordered set poset forest poset perfect matching Z-transformation graphs planar bipartite graph Hasse diagram connected graph bipartite graph planar graph tree forest. true true false [M. Trbovc Rebernak] Slovenski jezik Angleški jezik Diplomsko delo 2015-06-05 11:33:20 2016-04-21 13:54:31 2022-05-24 03:07:18 2021-05-08 03:39:31 2015 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.172.2(043.2) 22109192 URN:SI:UM:DK:BYNNT5ZE UN_Trbovc_Mateja_2015.pdf UN_Trbovc_Mateja_2015.pdf 1 E8CBCD2604FCFE87486B44FFF2FC435A 6ec32d0a6e11886dacd4240bfee3fcbc1f97e521353c0cf1497e5dae2030b234 ad8ba710-7c0b-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=72356 Fakulteta za naravoslovje in matematiko 0 0 0