|
| |
|
|
Hry na grafech
Gavenčiak, Tomáš ; Kratochvíl, Jan (vedoucí práce) ; Pergel, Martin (oponent)
V této práci studujeme některé vlastnosti jedné hry typu cop&robber, při které se dva hráči - Policista (Cop) a Lupič (Robber) - střídají v tázích na konečném neorientovaném grafu. Oba hráči se pohybují rychlostí nanejvýš jedna hrana za tah a znají v každém okamžiku celý stav hry. Pokud se Policista kdykoli ocitne na stejném poli jako Lupič, vyhraje Policista. Pokud k tomuto nikdy nedojde, vyhrává Lupič. Hry tohoto typu jsou důležité jako modely prohledávání grafu i pro svou souvislost s invarianty zdvihu grafu. Zabýváme se blíže vlastnostmi grafů, na kterých existuje výherní strategie pro Policistu (tzv. cop-win grafy), a hledáním nejlepších strategií pro oba hráče. Již dříve bylo známo, že počet tahů, za který je Policista schopen vyhrát na jakémkoli cop-win grafu na n vrcholech je zhora omezen n 3, a existují grafy vyžadující n 4. V této práci ukazujeme, že tento počet je právě n 4.
|
|
|
Combinatorial applications of linear algebra
Tesař, Marek ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
Nakrytie grafu G do grafu H je "lokálny izomorfizmus": zobrazenie vrcholov grafu G na vrcholy grafu H také, že pre všetky v V (G), okolie vrchola v je zobrazené bijektívne na okolie (v H) obrazu v. My študujeme výpočetnú zložitosť problému nakrytia na graf H (rozhodnútie či pre daný graf G existuje nakrytie do H), kde graf H je regulárny graf na 8 vrcholoch, jeho hrany majú dve farby, pričom hrany jednej farby tvoria dva disjunktné 4-cykly. Podávame tu plnú charakterizáciu problému nakrytia pre takéto 3 regulárne grafy. Polynomiálne prípady riešime pomocou prevodu na sústavu lineárnych rovníc a tiež ukážeme niektoré grafy, pre ktoré táto metóda nefunguje (napriek tomu, že problém nakrytia je polynomiálne riešitelný).
|
|
|
Geometrické reprezentace grafů
Klavík, Pavel ; Kratochvíl, Jan (vedoucí práce) ; Pergel, Martin (oponent)
Průnikové grafy jsou podrobně studovaným odvětvím teorie grafů. Složitostní otázky rozpoznávání jsou zkomány již řadu let. Pro zadáný graf se ptáme, zda patří do do dané třídy. V této práce představujeme nový problém rozšiřování částečných reprezentací. Pro tento problém je vedle grafu zafisována část reprezentace. Ptáme se, zda je možné tuto částečnou reprezentaci rozšířit na celý graf. Tento problém je alespoN tak těžký jako rozpoznávání. Zabýváme se problémem rozšiřování pro několik tříd průnikových grafů. Vyřešili jsme rozšiřování intervalových grafů v čase O(n2) a vlastních intervalových grafů v čase O(mn). Pomocí metody popsané Golumbicem umíme rozšířit provnalné a permutační grafy v čase O( · m). Mezi některými třídami jsou známy rovnosti, například mezi jednotkovými intervalovými grafy a vlastními intervalovými grafy. Překvapivě v případě rozšiřování je musíme rozlišit. Podobně ukazujeme, že v případě rozšířování funkčních grafů a doplňků provnatelných grafů se jedná o zcela jiné problémy.
|
|
| |
|
|
Výpočetní složitost v teorii grafů
Ondráčková, Eva ; Kratochvíl, Jan (vedoucí práce) ; Sgall, Jiří (oponent)
Seidelovo přepnutí je grafová operace, která změní hrany vycházející z daného vrcholu tak, aby sousedil s právě těmi vrcholy, které původně nebyly jeho sousedy; zbytek grafu zůstane nezměněn. Dva grafy nazveme ekvivalentní v přepnutí, pokud lze pomocí posloupnosti přepnutí jeden z nich převést na izomorfní tomu druhému. V této práci studujeme výpočetní složitost problému S(P) pro určitou grafovou vlastnost P: je daný graf G ekvivalentní v přepnutí nějakému grafu, který má vlastnost P? Neprve podáváme přehled známých výsledků, vlastností P, pro které je problém S(P) polynomiální, i těch, pro které je NP-úplný. Poté ukážeme NP-úplnost následujícího problému pro každé c (0; 1): lze daný graf G přepnout tak, aby obsahoval kliku velikosti alespoň cn, kde n je počet vrcholů grafu G? Zabýváme se také problémem pro pevně zvolený graf H rozhodnout, zda je daný graf G ekvivalentní v přepnutí nějakému H-prostému grafu. Ukážeme, že je-li H izomorfní spáru, tento problém je polynomiální. Dále podáváme charakterizaci grafů, které jsou ekvivalentní v přepnutí nějakému K1;2-prostému grafu, pomocí deseti zakázaných indukovaných podgrafů, z nichž každý má pět vrcholů.
|
|
|
Omezování vlastnického práva k půdě (příčiny a právní formy)
Kratochvíl, Jan ; Franková, Martina (vedoucí práce) ; Žákovská, Karolina (oponent)
V rámci účinnosti zejména nové právní úpravy soukromého práva a i v rámci změn v úpravě veřejnoprávní se tato diplomová práce pokouší o opodstatnění a rozvedení jednotlivých forem omezování vlastnického práva k půdě. Též se zabývá specifikací příčin, které k těmto omezením vedou a vyzdvihnutím podstaty vlastnického práva. Důraz je zde krom rozvedení potřebných právních pojmů věnován i analýze nových právních zásad, institutů a ustanovení a také jejich dopadu na právní prostředí. Dle věcného dělení práce analyzuje a vysvětluje dle dosavadní i nové právní úpravy vybraná omezení vlastnického práva k půdě v rámci rovin soukromého i veřejného práva. Evidence těchto jednotlivých omezení a i případné náhrady jimi způsobených újem mají také svůj význam, a proto jsou též v práci uvedeny.
|
|
|
Metafyzické základy filozofie Ladislava Klímy
Kratochvíl, Jan ; Hogenová, Anna (oponent) ; Rybák, David (oponent)
Práce je věnována rozboru metafyzických základů filozofie českého spisovatele a myslitele Ladislava Klímy. Zachycuje jeho polemiku se starší filozofickou tradicí a vlastními inspiračními zdroji a odhaluje zásadní kontradikce výsledného celku - egosolismu. Těžiště práce leží v analýze přechodu jistého metafyzického vidění světa ve specifický etický apel a s tím související kritikou křesťanské víry tak, jak ji Klíma vnímal. Ta je mnohem více emocionální, než racionální, tato emotivita je ilustrována ukázkami z Klímovy beletristické tvorby. Z nich je rovněž dovozováno ulpívání na hlediscích tradiční metafyziky. V závěru práce jsou shrnuta východiska Klímova filozofování, z nichž popsané kontradikce nutně vyplývají. Je ovšem navržen takový způsob čtení Klímova díla, který je vůči myšlenkové nesoudržnosti výsledného intelektuálního konstruktu indiferentní.
|
|
| |
|
|
Chromatic invariants in graph drawing
Štola, Jan ; Kratochvíl, Jan (vedoucí práce) ; Valtr, Pavel (oponent)
V této práci se zabýváme vlivem barevnosti grafu na existenci různých druhů ortogonálních nakreslení tohoto grafu. Studujeme otázku, jak velké můžeme volit kb,n tak, aby každý graf barevnosti nejvýše kb,n měl n-rozměrné ortogonální nakreslení s hranami s nejvýše b ohyby. kb,n nazývá1ne multipartitním číslem reprezentace/ nakreslení. Pro ortogonální nakreslení, v nichž jsou vrcholy reprezentovány úsečkami v IRn, je v práci multipartitní číslo odvozeno přesně pro všechna n. Přesná hodnota je určena taktéž pro viditelnostní reprezentace pomocí obdélníků a čtverců. Navíc jsou vylepšeny nejlepší známé horní a dolní odhady pro trojrozměrné ortogonální nakreslení pomocí obdélníků a hranolů. Dolní odhad je zvýšen ze 3 na 22 a horní snížen ze 183 na 42. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.