|
|
Kombinatorické úlohy o mincích
Hamáček, Jan ; Slavík, Antonín (vedoucí práce) ; Fiala, Jiří (oponent)
Práce se zabývá otázkami reprezentace zvolené částky pomocí libovolného množství mincí předep- saného typu. V první kapitole odvozujeme vzorce pro počet nereprezentovatelných částek a hodnotu největší nereprezentovatelné částky pro dvoumincové systémy. Dále ukazujeme grafový algoritmus pro výpočet Frobeniova čísla a d·kaz NP-úplnosti rozhodovacího problému reprezentovatelnosti zvolené částky v systému s více mincemi. V druhé kapitole se zabýváme výpočtem počtu reprezentací částky zvláš' v systémech o dvou nebo více mincích. Ve třetí kapitole se věnujeme otázce, zda lze ve zvoleném systému mincí použít hladový algoritmus pro nalezení reprezentace částky pomocí nejmenšího možného množství mincí. Poslední kapitola obsahuje sbírku řešených logických úloh o mincích. 1
|
|
|
Rozložitelnost grafů na souvislé podgrafy
Musílek, Jan ; Pangrác, Ondřej (vedoucí práce) ; Fiala, Jiří (oponent)
V roce 2003 prezentovali J. Barát a C. Thomassen na konferenci Eurocomb definici a základní výsledky z oblasti hranové rozložitelnosti grafů. Rozložitelností rozumíme možnost pokrytí množiny hran grafu disjunktními souvislými podgrafy předepsaných velikostí. Graf je rozložitelný, existuje-li takové pokrytí pro všechny možné předepsané velikosti podgrafů. Naše práce se zabývá především rozložitelností hranovou, o níž je známo méně výsledků, než o vrcholové rozložitelnosti. Dokážeme, že rozložitelnost je implikovaná existencí dominujícího tahu a tedy i hranovou 4-souvislostí. Dále se zabýváme omezenou variantou rozložitelnosti, definujeme pojem spektra rozložitelnosti a dokazujeme o něm několik tvrzení platných pro všechny grafy. Omezenou rozložitelnost pak podrobněji zkoumáme na některých specifických třídách grafů.
|
|
|
Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů
Masařík, Tomáš ; Fiala, Jiří (vedoucí práce)
Tato diplomová práce se zabývá hranovou značkovatelností grafu v závislosti na parametrech p, q a λ. Pro parametry p = 2 a q = 1 jsme dokázali dichotomii. Tedy, že problém λ′ (2,1)-značkovatelnosti grafu je polynomiální pro λ ≤ 4 a NP- úplný pro λ > 4. Hranice NP-úplnosti se tedy posouvá o jedna oproti vrcholové variantě problému, λ(p,q)-značkovatelnosti grafu, která byla již vyřešena dříve. Pro polynomiální případy získáme poměrně snadnou charakterizaci pomocí kruž- nic a cest rozšířených o několik dalších vrcholů. K NP-převodu využíváme jeden z poměrně klasických NP-úplných problémů Monotónní všude různý 3-SAT. Celý důkaz převodu je rozdělen na čtyři části, neboť kromě rozlišení sudých a li- chých λ, bylo třeba vyvořit ještě speciální převody pro λ = 5 i λ = 6. 1
|
|
| |
|
|
Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů
Masařík, Tomáš ; Fiala, Jiří (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Tato diplomová práce se zabývá hranovou značkovatelností grafu v závislosti na parametrech p, q a λ. Pro parametry p = 2 a q = 1 jsme dokázali dichotomii. Tedy, že problém λ′ (2,1)-značkovatelnosti grafu je polynomiální pro λ ≤ 4 a NP- úplný pro λ > 4. Hranice NP-úplnosti se tedy posouvá o jedna oproti vrcholové variantě problému, λ(p,q)-značkovatelnosti grafu, která byla již vyřešena dříve. Pro polynomiální případy získáme poměrně snadnou charakterizaci pomocí kruž- nic a cest rozšířených o několik dalších vrcholů. K NP-převodu využíváme jeden z poměrně klasických NP-úplných problémů Monotónní všude různý 3-SAT. Celý důkaz převodu je rozdělen na čtyři části, neboť kromě rozlišení sudých a li- chých λ, bylo třeba vyvořit ještě speciální převody pro λ = 5 i λ = 6. 1
|
|
|
Obtížné problémy vzhledem k parametru různorodost sousedství
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Fiala, Jiří (oponent)
Parametrizovaná složitost je oblast teoretié informatiky zabývající se výpočetní složitostí pro- blémů měřenou nikoliv pouze délkou vstupu, ale i nějakým jeho parametrem. "Různorodost soused- ství" je nový strukturální parametr grafu, který je atraktivní především proto, že pro grafy s pevnou různorodostí sousedství se stávají efektivně řešitelnými i některé problémy, jež zůstávají těžké pro jiné parametry s různorodostí sousedství neporovnatelnými. V této práci nově ukazujeme efektivní řeši- telnost vzhledem k různorodosti sousedství pro tři problémy těžké vzhledem ke stromové šířce. To tvoří hlavní část této práce a jedná se o náš vlastní výzkum. Dále pak práce obsahuje přehled další zajímavý problémů a také shrnutí současného stavu v oblasti parametrů pro řídké a husté grafy. 1
|
|
|
Some point-free aspects of connectedness
Jakl, Tomáš ; Pultr, Aleš (vedoucí práce) ; Fiala, Jiří (oponent)
V této práci ukážeme Stoneovu větu o reprezentaci, která je také známa pod názvem Stoneova dualita, v bezbodovém kontextu. Předvedený důkaz je bezvýběrový, a protože se nemusíme starat o jednotlivé body, je mnohem jednodušší než původní důkaz. Ukážeme, že pro každý nekonečný kardinál κ jsou protějšky κ-úplných Booleových algebrer κ-bazicky nesouvislé Stoneovy framy. Také předvedeme přesnou charakterizaci morfismů, které jsou v ko- responenci s κ-úplnými Booleovskými homomorfismy. Ikdyž Booleanizace není obecně funktoriální, v části duality extremálně nesouvislých Stoneových framů funktoriální je a dokonce tvoří ekvivalenci kategorií. Na konci práce se zaměříme na De Morganovské (respektive extremálně nesouvislé) framy a ukážeme jejich novou charakterizaci pomocí jejich superhustých sublokálů. Naproti tomu jsou metrizovatelné framy, které nemají žádný netriviální su- perhustý sublokál, a proto nikdy není jejich netriviální Čech-Stoneova kom- paktifikace metrizovatelná. 1
|
|
|
Structural Graph Theory
Zamora, José ; Loebl, Martin (vedoucí práce) ; Sereni, Jean Sébastien (oponent) ; Fiala, Jiří (oponent)
V práci studujeme čtyři problémy ze strukturální teorie grafů. Nejprve se zabýváme strukturou grafů které mají nikde nenulový 5-tok. Podáme charakteri- zaci takových grafů pomocí existence (1, 2)−faktorů. Ve druhé části zavedeme nový typ dekorace vrcholů grafu, kterému říkáme aditivní barvení. Aditivní barvení je injektivní barvení s omezeními danými grafem. Studujeme strukturu grafů které mají tuto dekoraci, a související algoritmické otázky. Ve třetí časti studujeme hypotézu kterou formuloval před asi dvaceti lety R. Stanley: je pravda, že U-polynom rozlišuje neizomorfní stromy? Dokážeme tuto hypotézu pro stromy- housenky bez vrcholů stupně dva. O tento výsledek se v minulých letech snažila řada vědců, například S. Noble. Ve čtvrté části studujeme strukturu nekonečných grafů které mají uplný graf jako minor nebo topologický minor. Klíčová slova: graf, nikde nenulový tok, faktor grafu, barvení grafů, izomorfismus grafů, strom, U-polynom, minor, topologický minor.
|
|
|
Barevnost grafů na plochách
Tůma, Vojtěch ; Dvořák, Zdeněk (vedoucí práce) ; Fiala, Jiří (oponent)
V této práci se zabýváme rozšiřováním 4-obarvení cyklu do zbytku grafu. Ukážeme, že pro rovinný 3-barevný graf takový, že vnější stěna O má velikost 4 nebo 5 a všechny ostatní stěny mají velikost 3, se otázka rozšiřitelnosti předbarvení O redukuje na otázku rozšiřitelnosti předbarvení do 3 malých základních grafů. Dále podobným způsobem klasifikujeme i situaci, kdy je v grafu stěna velikosti 4 různá od O. 1
|
|
|
Meze pro vzdálenostně podmíněné značkování grafů
Kupec, Martin ; Fiala, Jiří (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Problém λ − L(p, q)-značkování je přiřadit vrcholům grafu značky {0, . . . , λ} tak, aby sousední vrcholy měly značky od sebe vzdálené alespoň p a vrcholy se společným sousedem značky od sebe vzdáleny alespoň q. Zabýváme se výpočení složitostí tohoto problému a stanovujeme hraniční hodnoty λ, p a q, pro které se tento problém stává NP těžký. Důkaz je veden promocí dvou různých redukcí. Jedna je z NAE-3SATu, druhá z problémů hranového dobarvení před- barveného grafu. 1
|
host ::
RSS.