Ročníkové projekty

Na této stránce je možné naleznout několik projektů vhodných jako ročníkový na naší fakultě. Mimo tyto se rád dohodnu na projektu, který bde zajímat jak vás tak mě. Mezi moje zájmy primárně patří (ale určitě se na tyto neomezuji!): Jako programovací jazyk bych primárně předpokládal jazyk C. Protože většina problémů je orientovaná na grafy, jistě využijeme balík knihovny nauty, který generuje neisomorfní grafy. Většina (ne-li všechny) mnou nabízené projekty jsou vhodné pro Studentský Fakultní Grant.

Rovinné grafy a pokrytí klikami

V článku [Borodin-Ye] autoři popisují, že je možné pro rovinné grafy naleznout pořadí vrchloů takové, že v tomto pořadí je možné pokrýt sousedy daného vrcholu pomocí omezeně mnoha klik (konkrétně třemi). Metoda je značně nekonstruktivní a není jasné jak je tato úloha algoritmicky náročná.
V článku je možné naleznout algoritmus vyžadující čas $O(n^5),$ který ale jistě nebude optimální.

Cíl projektu

Projekt je vhodný pro návaznost na Bakalářskou práci.

Chordální doplnění a stromová šířka

Chordální grafy jsou grafy, které jsou triangulované. Alternativně je možné říci, že v takovýchto grafech není možné naleznout indukovaný cyklus delší než 3. Pro graf $G$ je zajímavé nalezení jeho chordálního nadgrafu $H$ (tj. grafu na stejné množině vrocholů, a tedy jen přidanými hranami). Při řešení tohoto problému je možné se soustředit na dvě kritéria: co nejmenší počet doplněných hran a co nejmenší klikovost grafu $H$ (v tomto případě optimalizujeme tzv. stromovou šířku). Obecně optimalijeme-li jedno či druhé, dostáváme jiné grafy. Jako velice zajímavá se jeví otázka existence třídy grafů, pro kterou optimalizujeme-li dle prvního kritéria, bude výsledný graf optimální i co do druhého kritéria.

Cíl projektu

Projekt je vhodný pro návaznost na Bakalářskou práci. V té by bylo ideální ukázat, že nalezené třidy opravdu vyhovují.

Chordální souvisle-nesouvislé grafy

Pro chodální (triangulované) grafy dále platí, že jsou to průnikové grafy podstromů ve stromě. Tedy pro chordální graf $G=(V,E)$ existuje strom $T$ a kolekce jeho podstromů ${\cal T} = \{T_v\colon v\in V\}$ (tedy pro každý vrchol grafu $G$ jeden podstrom stromu $T$) taková, že $\{u,v\}\in E$ právě když $T_u \cap T_v\neq\emptyset.$ Pokud zobecníme definici chordáního grafu---povolíme více stromů k jednomu vrcholu---dostaneme velice obsáhlou třídu. Rád bych abychom se zamysleli nad omezením tohoto. Konkrétně každému vrcholu odpovídají nanejvýš (právě) dva podstromy a navíc jejich doplněk je souvislý (tedy opět podstrom). Tímto získáme, že doplněk takovéhoto grafu je chordální. Navíc platí, že tímto omezením na intervalových grafech získáme úplné grafy a sjednocení dvou úplných grafů---toto dává naději, že třída nebude příliš sloitá.

Cíl projektu

Testování vlastnosti (2,1)-souvislých jedniček

Pro čtvercovou matici $A\in \{0,1\}^{n\times n}$ a permutaci $\pi: [n]\rightarrow [n]$ definujeme matici $A^\pi$ jako matici vzniklou z matice $A$ přepermutováním sloupců dle permitace $\pi.$
O matici $A$ řekneme, že má vlastnost souvislých jedniček, pokud existuje permutace $\pi$ jejích sloupců taková, že každý řádek matice $A^\pi$ má podobu $0^*1^*0^*.$ Tedy má nejprve souvislý úsek nul následovaný úsekem jedniček a uzavírá opět úsek nul, přičemž každý takovýto úsek může být prázdný.
O matici $A$ řekneme, že má vlastnost (2,1)-souvislých jedniček, pokud existuje permutace $\pi$ jejích sloupců taková, že každý řádek matice $A^\pi$ má podobu $0^*1^*0^*$ nebo $0^*1^*01^*0^*.$

Cíl projektu