|
|
Dům na Obilním trhu
Čuláková, Michaela ; Ježková, Tereza (oponent) ; Kratochvíl, Jan (vedoucí práce)
Bakalárska práca sa zameriava na návrh budovy moderného transparentného úradu v Brne na Obilnom trhu. Vzhľadom na blízkosť komunitnej záhrady, Špilberku a necelistvosti odboru životného prostredia v Brne bol zvolený Inštitút životného prostredia. Okrem kancelárií budova poskytuje stravovanie,ubytovanie hosťujúcim spolupracovníkom a tiež priestory pre propagáciu úradu a to prednáškový sál a galériu. Svojou hmotou uzatvára južnú časť Obilného trhu a vďaka vertikálnej záhrade na fasáde zapadá do prostredia a prispieva k zlepšeniu mikroklímy.
|
|
|
Hamiltonovské kružnice v kubických grafech
Melka, Jakub ; Kratochvíl, Jan (vedoucí práce) ; Pergel, Martin (oponent)
V této práci studujeme složitost Thomasonova algoritmu na určité třídě kubických grafů. Tento algoritmus nad kubickými grafy najde druhou hamiltonovskou kružnici, pokud dostane první, a je nad těmito grafy deterministický. Otevřeným problémem je složitost tohoto algoritmu, ale našla se třída grafů, kde pro každý graf existuje hamiltonovská kružnice a na ní hrana, pro niž tento algoritmus udělá exponenciální počet kroků, než vydá výslednou hamiltonovskou kružnici. Cílem této práce bylo zjistit, zda se na této třídě chová algoritmus exponenciálně pro libovolně zadanou kružnici a libovolnou hranu na této kružnici.
|
|
|
Graph Drawing: Visualisation and Geometric Representations of Graphs and Networks
Vyskočil, Tomáš ; Kratochvíl, Jan (vedoucí práce) ; Felsner, Stefan (oponent) ; Kaiser, Tomáš (oponent)
Název práce: Kreslení grafů: Vizualizace a geometrické reprezentace grafů a sítí Autor: Tomáš Vyskočil Katedra: Katedra applikované matematiky Vedoucí: Prof. RNDr. Jan Kratochvíl, CSc., KAM Abstrakt: Tato práce se věnuje studiu reprezentací grafů. V kapitolách 2-4 studujeme průnikové grafy v rovině a v kapitole 5 studujeme problémy modi- fikací grafů pomocí jednoduchých operací. V části věnované průnikovým grafům se věnujeme následujícím. Ukážeme, že částečné 2-stromy jsou průnikové grafy úsečkových grafů. Dále ukážeme složitost rozpoznání průnikových grafů k lomených cest na mřížce a průnikových grafů ostrovů v rozšířené mřížce. V části věnované modifikacím grafů ukážeme FPT-algoritmus který řeší problém, zda můžeme získat rovinný graf ze vstupního grafu pomocí nejvýše k kontrahovaných hran a zobecnění tohoto problému. Klíčová slova: teorie grafů, reprezentace grafů, kombinatorika
|
|
| |
|
|
Extending Partial Representations of Graphs
Klavík, Pavel ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
V této práci se zabýváme geometrickými průnikovými reprezentacemi grafů. Pro danou třídu se známý problém rozpoznávání ptá, jestli graf na vstupu náleží do této třídy. Studujeme zobecnění tohoto problému nazvané rozšiřování částečných reprezen- tací. Vstup je tvořen grafem spolu s částečnou reprezentací, jinými slovy část grafu je předkreslena. Problém se ptá, jestli je možné tuto částečnou reprezentaci rozšířit na reprezentaci celého grafu. Tento problém studujeme pro třídy intervalových grafů, vlastních intervalových grafů, jednotkových intervalových grafů a chordálních grafˇu (ve formě reprezentací jako podstromy ve stromě). Popisujeme lineární algoritmy pro první dvě třídy a téměř kvadratický algoritmus pro jednotkové intervalové grafy. Pro chordální grafy uvažujeme různé verze problému a ukazujeme, že skoro všechny jsou NP-úplné. Přestože třídy vlastních a jednotkových intervalových grafů jsou si rovny, problém rozšiřování částečných reprezentací je rozlišuje. Jednotkové intervalové grafy kladou dodatečné podmínky týkající se přesných pozic intervalů. V práci popisujeme novou strukturu jednotkových intervalových reprezentací, která umožňuje tyto dodatečné...
|
|
|
Representations and Visualization of Graphs
Štola, Jan ; Kratochvíl, Jan (vedoucí práce) ; Valtr, Pavel (oponent) ; Wood, David (oponent)
The 3D visibility (graph) drawing is a graph drawing in IR3 where vertices are represented by 2D sets placed into planes parallel to xy-plane and the edges correspond to z-parallel visibility among these sets. We continue the study of 3D visibility drawing of complete graphs by rectangles and regular polygons. We show that the maximum size of a complete graph with a 3D visibility drawing by regular n-gons is O(n4). This polynomial bound improves signifficantly the previous best known (exponential) bound 6n3 3n1 3 26n.We also provide several lower bounds. We show that the complete graph K2k+3 (resp. K4k+6) has a 3D visibility drawing by regular 2k-gons (resp.(2k + 1)-gons). We improve the best known upper bound on the size of a complete graph with a 3D visibility drawing by rectangles from 55 to 50. This result is based on the exploration of unimodal sequences of k-tuples of numbers. A sequence of numbers is unimodal if it rst increases and then decreases. A sequence of k-tuples of numbers is unimodal if it is unimodal in each component. We derive tight bounds on the maximum length of a sequence of k-tuples without a unimodal subsequence of length n. We show a connection between these results and Dedekind numbers, i.e., the numbers of antichains of a power set P(1; : : : ; k) ordered by inclusion.
|
|
|
Výpočetní složitost v teorii grafů
Doucha, Martin ; Kratochvíl, Jan (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Tato práce zavádí dvě nové parametrizace grafových úloh zobecňující vrcholové pokrytí, které v hierarchii grafových parametrizací vyplňují část prostoru mezi vrcholovým pokrytím a klikovou šířkou. Dále zde zkoumáme parametrizovanou složitost hledání Hamiltonovské cesty a kružnice, klasického barvení grafu, problému Precoloring extension a Equitable coloring pro tyto nové parametrizace. Kromě problému Precoloring extension, který je pro jednu parametrizaci W[1]-těžký, se pro všechny ostatní problémy podařilo najít FPT algoritmus pro obě parametrizace. Hranici mezi třídami FPT a W[1] se tak u těchto problémů podařilo posunout blíže směrem k parametrizaci klikovou šířkou.
|
|
|
Výpočetní složitost v teorii grafů
Melka, Jakub ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
V předložené práci studujeme problém rekonstrukce grafu ze seznamu uzavřených okolí vrcholů tohoto grafu. Tento problém, původně zformulovaný V. Sósovou, budeme zkoumat z hlediska teorie parametrizované složitosti a zobecníme jej na problém rekonstruovatelnosti vzhledem ke třídám grafů. V této práci dokážeme, že tento problém leží ve třídě složitosti FPT vzhledem k parametru omezené stromové šířky a omezeného maximálního stupně nebo ke 2-degenerovaných grafům s omezeným počtem jistých indukovaných podgrafů, kde parametr je počet těchto podgrafů. Dále dokážeme, že problém rekonstruovatelnosti vzhledem ke třídě grafů s omezeným vrcholovým pokrytím leží ve třídě složitosti XP. Na závěr dokážeme vzájemnou nezávislost získaných výsledků.
|
|
|
Přenosové prostředky komunikace v dějinném vývoji
Kratochvíl, Jan ; Smetáček, Vladimír (vedoucí práce) ; Machytka, Jan (oponent)
Cílem této bakalářské práce je popsat vývoj vybraných přenosových prostředků komunikace v historii. Práci lze rozdělit na dvě části, ve kterých se postupně setkáváme s různými přenosovými prostředky. První se věnuje optickým telegrafním systémům od antiky přes pochodňové telegrafy do poloviny 17. stol. Druhá část je zaměřena na vyspělé telegrafy R. Hooka (1635-1703), C. Chappeho (1763-1805), A. N. Edelcrantze (1754-1821), G. Murraye (1761-1803). U přenosových prostředků je hlavně zkoumáno: dosah komunikace, její důvod, rychlost a utváření komunikačních sítí.
|
|
|
Computational Complexity in Graph Theory
Jelínková, Eva ; Kratochvíl, Jan (vedoucí práce) ; Manlove, David (oponent) ; Fiala, Jiří (oponent)
Název práce: Výpočetní složitost v teorii grafů Autor: Eva Jelínková Katedra: Katedra Aplikované Matematiky Vedoucí disertační práce: Prof. RNDr. Jan Kratochvíl, CSc., Katedra Aplikované Matematiky Abstrakt: Zabýváme se problémy teorie grafů, zejména z hlediska výpočetní složitosti. V první části práce se věnujeme výpočetní složitosti problémů sou- visejících se Seidelovým přepnutím grafů. Uvažujeme rozhodující problém, zda daný graf lze přepnout tak, aby obsahoval nejvýše daný počet hran. Dokážeme, že tento problém je NP-úplný, dokonce i pro grafy s omezenou hustotou. Částečně tak odpovídáme na otázku Matouška a Wagnera [Dis- crete Comput. Geom. 52, no. 1, 2014]. Popisujeme také nekonečně mnoho grafů H, pro které je NP-těžké rozhodnout, zda pro daný graf existuje graf, který je s ním ekvivalentní v přepnutí, a zároveň neobsahuje H jako induko- vaný podgraf. Tímto řešíme otevřený problém Kratochvíla, Nešetřila a Zýky [Annals of Discrete Math. 51, 1992]. Ve druhé části práce se zabýváme tématem párování s preferencemi. Zaměřujeme se na problém trhu s domy, konkrétně na model s duplicitními domy. Popisujeme 2-aproximační algoritmus pro maximální počet spoko- jených agentů v případě,...
|
host ::
RSS.