Title: | Přiřazovací úloha v hypergrafech |
Other Titles: | Assignment problem in hypergraphs |
Authors: | Lejbová, Terezie |
Advisor: | Čada Roman, Doc. Ing. Ph.D. |
Referee: | Holub Přemysl, Doc. RNDr. Ph.D. |
Issue Date: | 2023 |
Publisher: | Západočeská univerzita v Plzni |
Document type: | bakalářská práce |
URI: | http://hdl.handle.net/11025/53743 |
Keywords: | graf;hypergraf;párování;přiřazovací úloha |
Keywords in different language: | graph;hypergraph;matching;assignment problem |
Abstract: | Dokument popisuje rozdíly mezi párováním v neorientovaných grafech a neorientovaných hypergrafech. Úvodní kapitola slouží jako seznámení se základními pojmy teorie grafů, s úlohou matematické optimalizace a s výpočetní složitostí. Kapitola druhá se zabývá studiem neorientovaných neohodnocených grafů. Setkáme se v ní s několika větami, které hovoří o existenci a vlastnostech párování v neorientovaných grafech a ukážeme si, že výsledky těchto vět jsou ekvivalentní. Třetí kapitola nám podobným způsobem přiblíží problematiku párování v neorientovaných neohodnocených bipartitních hypergrafech. Definujeme zde několik nových pojmů a opět formulujeme větu, která hovoří o existenci párování v bipartitních hypergrafech a která zobecňuje jednu z vět, se kterou jsme se setkali v kapitole druhé. Na příkladu si ukážeme, že podmínku této věty už nelze zeslabit. Závěrem, pro srovnání problematiky párování v grafech a hypergrafech, volíme přiřazovací úlohu. Pracujeme zde nejen se slovní formulací, ale také s formulací pomocí lineárního programování. Porovnáváme způsoby řešení obou úloh, včetně časové složitosti. |
Abstract in different language: | This document describes the differences between matching in undirected graphs and matching in undirected hypergraphs. The introductory chapter serves as an introduction to the basic terms of graph theory, to the mathematical optimization problem and computational complexity. Chapter two deals with the study of undirected unweighted graphs. In it, we will encounter several theorems that talk about the existence and properties of pairing in undirected graphs, and we will show that the results of these theorems are equivalent. In a similar way, the third chapter will approach the problem of matching in undirected unweighted bipartite hypergraphs. Here we define several new terms and again formulate a theorem that speaks about the existence of pairings in bipartite hypergraphs. This theorem generalizes one of the theorems we encountered in chapter two. Using an example, we will show that its condition can not be weakened. Finally, to compare the problem of matching in graphs and hypergraphs, we choose the assignment problem. We work here not only with verbal formulation, but also with formulation using linear programming. We compare the methods of solving both problems, including the time complexity. |
Rights: | Plný text práce je přístupný bez omezení |
Appears in Collections: | Bakalářské práce / Bachelor´s works (KMA) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Prirazovaci_uloha_v_hypergrafech.pdf | Plný text práce | 1,29 MB | Adobe PDF | View/Open |
PO_Lejbova.pdf | Posudek oponenta práce | 883,56 kB | Adobe PDF | View/Open |
PV_Lejbova.pdf | Posudek vedoucího práce | 523,1 kB | Adobe PDF | View/Open |
prubeh_Lejbova.pdf | Průběh obhajoby práce | 192,67 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/53743
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.