|
|
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Binární matice neobsahující menší matici jako podmatici se stávají zajímavým tématem. V mé práci uvádím dva nové algoritmy pro testování, zda velká čtvercová binární matice obsahuje menší binární matici, a randomizovaný proces, který aproximuje uniformní náhodnou matici neobsahující danou matici. Toto umožní vědeckým pracovníkům testovat jejich hypotézy na náhodných maticích. Proto moje práce také obsahuje efektivní přenositelnou implementaci všech zmíněných algoritmů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Bounds on existence of odd and unique expanders
Hlásek, Filip ; Koucký, Michal (vedoucí práce) ; Šámal, Robert (oponent)
Práce se zabývá studiem existence expanderů a zaměřuje se především na liché a jednoznačné expandery. Naším nejdůležitějším výsledkem je tvrzení, že v každém grafu lze vybrat malou neprázdnou podmnožinu jeho vrcholů takovou, že každý jiný vrchol je s vybranou podmnožinou spojen alespoň dvěma hranami, nebo s ní není spojen vůbec. Jednoduchým důsledkem tohoto tvrzení je, že některé třídy jednoznačných expanderů nemohou existovat. Na druhou stranu popisujeme konfigurace parametrů, pro které nekonečné třídy expanderů jistě existují. Powered by TCPDF (www.tcpdf.org)
|
|
|
Skládání obdélníků
Pavlík, Tomáš ; Šámal, Robert (vedoucí práce) ; Mareš, Martin (oponent)
Tato diplomová práce se zabývá otevřeným problémem skládání obdélníků. Je možné naskládat obdélníky rozměrů 1/n x 1/(n+1) do jednotkového čtverce? Cílem práce je podrobná analýza tohoto problému a s ním spojeného algoritmu. Pozornost bude zaměřena hlavně na implementaci tohoto algoritmu a na studii jeho fungování. Powered by TCPDF (www.tcpdf.org)
|
|
|
Lipschitz mappings in the plane
Kaluža, Vojtěch ; Matoušek, Jiří (vedoucí práce) ; Šámal, Robert (oponent)
V této práci se zabýváme otevřenou Feigeho otázkou, která se ptá, jestli exis- tuje konstantně lipschitzovská bijekce každé n2 -bodové podmnožiny Z2 na pra- videlnou mřížku [n] × [n] pro každé n ∈ N. Dáme tuto otázku do vztahu s již vyřešeným problémem existence hustoty v R2 , která není jakobiánem žádného bi- lipschitzovského zobrazení. Tento problém byl vyřešen Buragem a Kleinerem [1] a nezávisle McMullenem [12]. Předvedeme práci Buraga a Kleinera, zanalyzujeme její vztah k Feigeho problému a navrhneme spojitou formulaci Feigeho otázky ve speciálním případě. Poté předvedeme konstrukci hustoty Buraga a Kleinera, uděláme několik pozorování ohledně vlastností této hustoty a následně zkonstru- ujeme hustotu, která je všude nerealizovatelná jako jakobián bilipschitzovského zobrazení. Dále se zabýváme naší spojitou formulací Feigeho otázky, uděláme ně- kolik pozorování o této otázce a nakonec se pokusíme tuto otázku zodpovědět s použitím dříve zkonstruované všude nerealizovatelné hustoty. Nicméně tento poslední úkol zůstává stále nesplněn. 1
|
|
|
Grupová souvislost grafů
Mohelníková, Lucie ; Šámal, Robert (vedoucí práce) ; Pangrác, Ondřej (oponent)
Název práce: Grupová souvislost graf· Autor: Lucie Mohelníková Katedra: Informatický ústav Univerzity Karlovy Vedoucí diplomové práce: Mgr. Robert 'ámal,Ph.D., Informatický ústav Univerzi- ty Karlovy Abstrakt: Zabývali jsme se grupovou souvislostí graf·, zejména pak Z2 2- a Z4- souvislostí. Implementovali jsme v jazyce C++ test, zda je graf grupově souvislý a pomocí něho hledáme grafy, které jsou grupově souvislé v jedné ze zkoumaných grup a v druhé nikoliv. Zkoumali jsme grafy, které vzniknou podrozdělením hran několika speciálních graf· např. K4 a krychle. Hlavním přínosem této práce je nalezení dvou graf·, které jsou Z4-souvislé a nejsou Z2 2-souvislé. Pomocí druhé nezávislé implementace testu na grupovou souvislost napsané v jazyce Prolog s využitím CSP jsme ověřili, že tyto grafy jsou Z4-souvislé. Analyticky jsme dokázali, že jeden z nalezených graf· není Z2 2-souvislý. Klíčová slova: grupová souvislost, toky, grupa
|
|
|
Minimal counterexamples to flow conjectures
Korcsok, Peter ; Šámal, Robert (vedoucí práce) ; Goodall, Andrew (oponent)
Říkáme, že graf má nikde-nulový k-tok, pokud umíme každé hraně přiradit její směr a přirozené číslo (<k) jako tok tak, aby pro každý vrchol $v$ byl celkový přítok a odtok stejný. Tutte vyslovil v roce 1954 hypotézi, že každý graf bez mostů má nikde-nulový 5-tok, a tato hypotéza je stále otevřená. Kochol v nedávné práci představil výpočetní metodu na dokázání, že minimální protipříklad nemůže obsahovat krátkou kružnici (až do délky 10). V této práci poskytujeme ucelený přehled této metody a protože Kochol nezveřejnil svou implementaci (a pro nezávislé ověrení metody), doplňujeme náš zdrojový kód, ktorý potvrzuje Kocholovy výsledky a rozšiřuje je: dokázali jsme, že minimální protipříklad neobsahuje kružnici kratší než 12. Powered by TCPDF (www.tcpdf.org)
|
|
|
Variants of Petersen coloring for some graph classes
Bílková, Hana ; Šámal, Robert (vedoucí práce) ; Rollová, Edita (oponent)
Normální obarvení - ekvivalentní verze petersenovského obarvení - je speciální dobré hranové obarvení kubických grafů pěti barvami. Každá hrana normálně obarveného grafu je normální, tj. používá spolu se svými čtyřmi sousedy pouze tři barvy nebo všech pět barev. Dle Jaegerovy hypotézy mají všechny kubické grafy bez mostů normální obarvení. Platnost hypotézy by dokázala například hy- potézu Cycle double cover. Zde řešíme slabší verzi Jaegerova problému. Hledáme dobré hranové pěti-obarvení takové, že alespoň část hran je normální. Pro obecné hranoly (generalized prisms) ukážeme obarvení s dvěma třetinami normálních hran, pro grafy bez krátkých kružnic obarvení s necelou polovinou normálních hran. Dále navrhneme nový pohled na normální obarvení - řetízky (chains). Po- mocí nich dokážeme tvrzení o nemožnosti výskytu právě jedné chyby ve skoro normálním obarvení a také několik tvrzení o řezech v normálně obarveném grafu plynoucí rovněž z nikde-nulového Petersenova toku. Nakonec prozkoumáme čtyř- cyklus v normálně obarveném grafu.
|
|
|
Optimisation using graph searching on special graph classes
Chejnovská, Anna ; Gavenčiak, Tomáš (vedoucí práce) ; Šámal, Robert (oponent)
Pro graf definujeme minimální pokrytí cestami jako nejmenší množinu vrcholově disjunktních cest, které pokrývají všechny vrcholy grafu. Tento problém je jedním z běžných zobecnění známého problému hledání Hamiltonovské cesty v grafu. V této práci vyjdeme ze článku Corneil et al. (2013), kde byl představen certifikující algoritmus pro hledání minimálního pokrytí cestami na cocomparability grafech (doplněk grafu relace neostrého částečného uspořádání). Tento algoritmus nejprve představíme, poté experimentálně prozkoumáme jeho robustnost vůči pěti operacím na hranách a vrcholech. Dopad těchto operací na velikost minimálního pokrytí cest rozebereme také teoreticky. Powered by TCPDF (www.tcpdf.org)
|
|
|
Duhové aritmetické posloupnosti a extremální množiny v mřížkách
Voborník, Jan ; Šámal, Robert (vedoucí práce) ; Pangrác, Ondřej (oponent)
Když jsou čísla $1,\ldots,tn$ obarvena $t$ barvami (každá je užita $n$-krát), existuje mezi nimi duhová aritmetická posloupnost délky $k$. (Duhová aritmetická posloupnost je taková, která nemá žádné dva členy stejné barvy.) Toto platí pro $t>k^3$. Označme $T_k$ nejmenší takové $t$, pro které to platí. Hypotéza Jungiće a spol. říká, $T_k=O(k^2)$. Problém souvisí s extremálními problémy diskrétních hyperkrychlí. Představujeme metodu s mřížkami (diskrétní hyperkrychle, které mohou obsahovat nerozlišitelné prvky), která může vést k vylepšení odhadu $T_k$ až na $O(k^2\log k)$. V práci vyřešíme několik extremálních problémů v mřížkách, které mají důsledky v různých partiích matematiky. Například pomocí mřížek dokážeme hranovou isoperimetrickou nerovnost pro Hammingovu krychli, nalezneme bipartitní graf s maximálním součtem druhých mocnin stupňů a konvexní množinu $M\subseteq [0,b]\times[0,a]$ maximalizující funkci $G(M)=\int_{x=0}^a \lambda_1(M_x)^2+\int_{y=0}^b \lambda_1(M_y)^2$. Powered by TCPDF (www.tcpdf.org)
|
|
|
Drawing graphs on surfaces of small genus
Tomášek, Jan ; Dvořák, Zdeněk (vedoucí práce) ; Šámal, Robert (oponent)
Přesto, že existuje mnoho algoritmů pro kreslení grafů na obecné plochy, existuje překvapivě malo funkčních implementací těchto algoritmů. Práce přináší přívětivé grafické rozhraní pro kreslení grafů na toru, které umožní přehledně kontrolovat výstup a posuzovat jeho kvalitu. Program podporuje zobrazení v mnohoúhelníkové reprezentaci a v třídimenzionálním prostoru. Práce se dále zabývá existujícími algoritmy pro nalezení pěkného nakreslení grafů na tyto plochy a diskutuje jejich použitelnost v praxi. Jeden algoritmus je vybrán a implementován včetně rozboru implementace a použitých datových struktur. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.