velikost textu

Délkově omezené řezy v grafech

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Délkově omezené řezy v grafech
Název v angličtině:
Length bounded cuts in graphs
Typ:
Diplomová práce
Autor:
Bc. Michal Berg
Vedoucí:
doc. Mgr. Petr Kolman, Ph.D.
Oponent:
Mgr. Pavel Dvořák
Id práce:
212716
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (N1801)
Obor studia:
Teoretická informatika (ITI)
Přidělovaný titul:
Mgr.
Datum obhajoby:
16. 9. 2019
Výsledek obhajoby:
Výborně
Jazyk práce:
Čeština
Klíčová slova:
řez, rovinný graf, stromová šířka, dynamické programování
Klíčová slova v angličtině:
cut, planar graph, tree width, dynamic programming
Abstrakt:
V této práci se budeme zabývat problémem délkově omezeného řezu, nazývaného také L-omezený řez. Ukážeme kombinatorický algoritmus pro hledání minimálního L-omezeného řezu na grafech omezené stromové šířky založený na dynamickém programování. Následně také ukážeme, že se tento algoritmus dá použít i pro hledání L-omezeného řezu na rovinných grafech. Také se podíváme na problém (dG(s, t) + 1)-omezeného řezu. Je známé, že tento problém je N P -těžký na obecných grafech. Ale to, jestli je N P -těžký i na rovinných grafech se speciálními vrcholy na vnější stěně, je otevřený problém. Pokusíme se nastínit způsob, kterým bychom možná mohli ukázat, že tento problém je řešitelný v polynomiálním čase.
Abstract v angličtině:
In this thesis we will focus on a problem of length bounded cut, also known as L-bounded cut. We are going to show a combinatorial algorithm for finding a minimal L-bounded cut on graphs with bounded treewidth based on dynamic programming. Then we going to show that this algorithm can also be used for finding minimal L-bounded cut on plannar graphs. We are also going to look at problem of (dG(s, t) + 1)-bounded cut. This problem is known to be N P -hard for general graphs. But it is an open problem whether this problem is also N P -hard on plannar graphs with special vertices on the outer face. We will try to outline a way, which might lead to showing that this problem is solvable in a polynomial time.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Michal Berg 806 kB
Stáhnout Abstrakt v českém jazyce Bc. Michal Berg 33 kB
Stáhnout Abstrakt anglicky Bc. Michal Berg 32 kB
Stáhnout Posudek vedoucího doc. Mgr. Petr Kolman, Ph.D. 82 kB
Stáhnout Posudek oponenta Mgr. Pavel Dvořák 87 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Roman Barták, Ph.D. 152 kB