|
|
Computational and structural apects of interval graphs and their variants
Novotná, Jana ; Kratochvíl, Jan (vedoucí práce) ; Jelínek, Vít (oponent)
Intervalové grafy, průnikové grafy úseček (intervalů) na reálné přímce, hrají klíčovou roli při studování algoritmů a specifických strukturálních vlastností. Velmi studovanou třídou jsou také jednotkové intervalové grafy, vlastní podtřída intervalových grafů, kde každý interval má jednotkovou délku. V práci se věnu- jeme smíšeným jednotkovým intervalovým grafům, grafům vzniklým zobecněním jednotkových intervalových grafů, kde každý interval má stále jednotkovou délku, ale může být různého typu (uzavřený, otevřený, polouzavřený). Tato drobná modi- fikace zahrnuje výrazně širší třídu grafů, například smíšené jednotkové intervalové grafy nejsou na rozdíl od jednotkových grafů spáruprosté. Heggernes, Meister a Papadopoulos přišli s bublinkovým modelem, takovou reprezentací jednotkových intervalových grafů, která se jeví užitečná při konstrukci různých algoritmů. Tento model rozšiřujeme na třídu smíšených intervalových grafů. Původní bublinkový model využili autoři Boyaci, Ekim a Shalom, kteří s jeho pomocí dokazovali, že problém největšího řezu v jednotkovém intervalovém grafu je polynomiální. V jejich důkazu jsme však objevili nejspíše neopravitelnou chybu. Dalším přínosem práce jsou ukázky využití našeho rozšířeného bublinkového mod- elu, na němž stavíme subexponenciální algoritmus pro problém největšího řezu...
|
|
|
Intersection representations of graphs
Töpfer, Martin ; Jelínek, Vít (vedoucí práce) ; Pangrác, Ondřej (oponent)
V této diplomové práci zkoumáme podtřídy vnějškových (outer) a uzem- něných (grounded) string grafů. Stringem rozumíme omezenou spojitou křivku v rovině. Průniková reprezentace grafu pomocí stringů je množina stringů, kde každý string odpo- vídá jednomu vrcholu z původního grafu. Dva stringy se protínají právě tehdy, když mezi jejich odpovídajícími vrcholy vedla v původním grafu hrana. Graf je vnějškový string graf, pokud existuje jeho reprezentace, kde jsou všechny stringy uvnitř disku a každý string má jeden ze svých konců na hranici disku. Obdobně je graf uzemněný string graf, pokud existuje jeho reprezentace, ve které má každý string jeden svůj konec na společné přímce a zbytky všech stringů jsou na stejné straně od hraniční přímky. V diplomové práci uvádíme přehled tříd string grafů a dokazujeme několik tvrzení ohledně vzájemné inkluze těchto tříd. K tomu nám slouží lemma, díky kterému umíme předepisovat u vnějško- vých a uzemněných grafů pořadí, v jakém se vyskytují na hraniční přímce (resp. hraniční kružnici) konce jednotlivých stringů. V druhé části práce dokazujeme, že rozpoznávání vnějškových string grafů je NP-těžké. 1
|
|
|
The complexity of constrained graph drawing
Hora, Martin ; Jelínek, Vít (vedoucí práce) ; Fink, Jiří (oponent)
Označkované nakreslení rovinného grafu G je uspořádaná dvojice (G, g) sklá- dající se z rovinného nakreslení G grafu G a z funkce g, jež přiřazuje popisky (barvy) jeho stěnám. V práci se zabýváme problémem Embedding Restriction Satisfiability (ERS), který řeší, zda má daný graf označkované nakreslení splňující předepsanou sadu podmínek. ERS je relativně nový problém, a tak se toho o něm zatím mnoho neví. Nicméně má velký potenciál. Zobecňuje totiž několik problémů hledajících specifická nakreslení grafů, jako je například problém částečně vno- řené rovinnosti (Partially Embedded Planarity). ERS se tedy může stát jedním z ústředích problémů v oblasti kreslení rovinných grafů. V této práci zkoumáme výpočetní složitost ERS. Jednak ukážeme, že ERS je NP-úplné, a poté vyšetříme složitost několika omezených verzí tohoto problému. Cílem je najít hranici mezi NP-těžkými a polynomiálními variantami. 1
|
|
|
Enumeration of polyomino fillings
Karpilovskij, Mark ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent)
V práci dokazujeme dva nové výsledky o 0-1-vyplněních skew diagramů, které neobsahují dlouhé rostoucí a klesající řetězce. V první polovině práce ukážeme, že pro velkou třídu skew diagramů existuje bijekce mezi řídkými vyplněními bez rostoucího řetězce dané délky a řídkými vyplněními bez klesajícího řetězce stejné délky. Ve druhé polovině práce zobecníme známou nerovnost mezi počtem řídkých vyplnění skew diagramu bez rostoucího řetězce délky 2 a počtem řídkých vyplnění bez klesajícího řetězce délky 2 na všechna možná 0-1-vyplnění. 1
|
|
|
Structural properties of hereditary permutation classes
Opler, Michal ; Jelínek, Vít (vedoucí práce) ; Valtr, Pavel (oponent)
Permutační třída C je splittovatelná pokud je obsažena v mergi svých dvou vlastních podtříd, a je 1-amalgamovatelná pokud pro libovolné permutace σ, τ ∈ C, každá s jedním vyznačeným prvkem, dokážeme najít permutaci π ∈ C, která obsahuje σ i τ tak že jejich vyznačené prvky splývají. V této práci zkoumáme 1-amalgamovatelnost a splittovatelnost permutačních tříd. Již dříve bylo dokázáno, že nesplittovatelnost implikuje 1-amalgamovatelnost. My ukážeme, že tyto dvě vlastnosti permutačních tříd nejsou ekvivalentní nalezením permutační třídy, která je splittovatelná a zároveň 1-amalgamovatelná. Navíc ukážeme, že existuje nekonečně mnoho takových permutačních tříd. Naše konstrukce je založená na konceptu LR-nafouknutí nebo více obecně na dědičných 2-obarvení, které v této práci také zavedeme a které by mohly být zajímavé i mimo naše použití. 1
|
|
|
Algoritmus pro dokreslování rovinných nakreslení
Hora, Martin ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Tento text se zabývá problémem dokreslování rovinných grafů. Vstupem pro- blému je graf G, jehož podgraf je již nakreslen do roviny. Cílem je pak rozhodnout, zda lze do roviny dokreslit i zbytek grafu G, a získat tak rovinné nakreslení G. Již bylo dokázáno, že lze dokreslitelnost rovinných grafů řešit v lineárním čase. Avšak všechny známé lineární algoritmy jsou poměrně komplikované, a pravděpodobně proto nebyla zveřejněna žádná jejich implementace. V práci představíme nový jednodušší lineární algoritmus řešící dokreslitelnost a dokážeme jeho korektnost. Dále pak k této práci přiložíme implementaci tohoto algoritmu v programovacím jazyce C++. 1
|
|
|
Hereditary classes of binary matrices
Kučera, Stanislav ; Jelínek, Vít (vedoucí práce) ; Klazar, Martin (oponent)
Intervalové minory binárních matic byly zavedeny Jacobem Foxem při vý- zkumu Stanleyho-Wilfových limit. Prozkoumáme, co se dá odvodit z jejich vztahu s teorií neobsahování podmaticových vzorů, což je velmi populární oblast diskrétní matematiky. Začneme charakterizací matic neobsahujících malé intervalové mi- nory. Poté se podíváme na třídy matic uzavřené na intervalové minory a najdeme takové třídy, které nelze popsat pomocí konečně mnoha zakázaných intervalových minorů. Také zadefinujeme a prozkoumáme variantu klasické Turánovské otázky zkoumané v oblastech kombinatoriky permutací a binárních matic a kombinato- rické geometrie. 1
|
|
|
Průnikové reprezentace grafů
Töpfer, Martin ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Průnikový graf je graf, ve kterém mezi dvěma vrcholy vede hrana, právě když jim odpovídající objekty se protínají. Tato práce se zabývá průnikovými grafy L-útvarů (tzv. L-grafy) a jejich speciálním případem, kdy konce všech L-útvarů jsou na jedné přímce (tzv. vnějškovými L-grafy). Po přehledu, co platí o L-grafech, používáme podobné postupy na vnějškové L-grafy. Ukážeme, že intervalové grafy, tětivové grafy (circular graphs) a vnějškově rovinné grafy jsou vnějškové L-grafy. Poté charakterizujeme vnějškové L-grafy pomocí uspořádání vrcholů bez zakázaných vzorů. Powered by TCPDF (www.tcpdf.org)
|
|
|
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)
|
|
|
Structure and enumeration of permutation classes
Karpilovskij, Mark ; Jelínek, Vít (vedoucí práce) ; Balko, Martin (oponent)
Definujeme operaci složení dvou dědičných tříd permutací pomocí standardního skládání permutací jako funkcí a zkoumáme vlastnosti a strukturu permutačních tříd s ohledem na tuto operaci. Převážně se zabýváme otázkou, zda lze danou permutační třídu složit z jejích vlastních podtříd. Ukážeme příklady tříd, které lze složit ze dvou vlastních podtříd, příklady tříd, které jdou složit ze tří, ale ne ze dvou vlastních podtříd a také několik příkladů tříd, které nelze složit z žádného konečného počtu vlastních podtříd. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.