Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Čada Roman, Doc. Ing. Ph.D. | |
dc.contributor.author | Lejbová, Terezie | |
dc.contributor.referee | Holub Přemysl, Doc. RNDr. Ph.D. | |
dc.date.accepted | 2023-6-19 | |
dc.date.accessioned | 2023-08-02T10:47:28Z | - |
dc.date.available | 2022-10-3 | |
dc.date.available | 2023-08-02T10:47:28Z | - |
dc.date.issued | 2023 | |
dc.date.submitted | 2023-5-24 | |
dc.identifier | 93329 | |
dc.identifier.uri | http://hdl.handle.net/11025/53743 | - |
dc.description.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. | cs |
dc.format | iv. s., 26 s. | |
dc.language.iso | cs | |
dc.publisher | Západočeská univerzita v Plzni | |
dc.rights | Plný text práce je přístupný bez omezení | |
dc.subject | graf | cs |
dc.subject | hypergraf | cs |
dc.subject | párování | cs |
dc.subject | přiřazovací úloha | cs |
dc.title | Přiřazovací úloha v hypergrafech | cs |
dc.title.alternative | Assignment problem in hypergraphs | en |
dc.type | bakalářská práce | |
dc.thesis.degree-name | Bc. | |
dc.thesis.degree-level | Bakalářský | |
dc.thesis.degree-grantor | Západočeská univerzita v Plzni. Fakulta aplikovaných věd | |
dc.thesis.degree-program | Matematika a její aplikace | |
dc.description.result | Obhájeno | |
dc.description.abstract-translated | 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. | en |
dc.subject.translated | graph | en |
dc.subject.translated | hypergraph | en |
dc.subject.translated | matching | en |
dc.subject.translated | assignment problem | en |
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.