Bakalářské a diplomové práce

Nabízím níže popsaná témata na bakalářské a diplomové práce. Pokud vás některé z nich zaujme, nebo byste měli zájem řešit práci na nějaké obdobné téma, neváhejte mě kontaktovat.

  • Zlomková barevnost grafů: Zlomková barevnost je varianta barevnosti grafu založená na relaxaci celočíselného lineárního programu popisujícího normální barevnost. Cílem práce by bylo studovat zlomkovou barevnost vhodně zvolené třídy grafů (např. nějaké speciální podtřídy rovinných grafů a pod., dle zajmu řešitele a požadované obtížnosti práce).
  • Přesné výsledky ve strukturální teorii grafů: Základní otázkou strukturální teorie grafů je popis tříd grafů bez předepsaných podobjektů (standardním případem je Kuratovského věta, že grafy bez K5 a K3,3 jako minoru či podrozdělení jsou přesně rovinné grafy). Přesné popisy jsou ale známé jen pro několik málo speciálních grafů. Cílem práce by bylo nalézt další takové popisy (pro bakalářskou či diplomovou práci např. v ještě nepříliš studované oblasti grafových imerzí; pro disertační práci lze zvážit i obtížnější problémy).
  • Algoritmy pro speciální třídy grafů: Pro některé výpočetní problémy, které jsou obecně obtížné, existuji algoritmy pro speciální třídy grafů (rovinné grafy, geometricky reprezentované grafy, ...). Cílem práce by bylo prakticky implementovat nějaký takový algoritmus, srovnat jeho efektivitu s nejlepšími obecnými algoritmy pro daný problém, a případně studovat jeho možná vylepšení.
  • 4-kritické grafy obvodu 5 na pochách omezeného rodu: Graf je 4-kriticky, má-li barevnost 4, ale každý jeho podgraf má barevnost 3. Jinak řečeno, graf lze obarvit 3 barvami, právě když neobsahuje 4-kriticky podgraf. Pro grafy obvodu alespoň 5 nakreslené na nějaké pevné ploše existuji strukturální výsledky popisující, jak takové 4-kritické podgrafy mohou vypadat. Tyto výsledky ale nedávají přesný seznam možných 4-kritických grafů (s výjimkou ploch rodu nejvýše 2). Cílem práce by bylo přesně popsat 4-kritické grafy bez trojúhelníku nakreslitelné na některé další plochy. Vhodné spíše na diplomovou práci nebo jako základ disertační práce.
  • Barevnost grafů velkého maximálního stupně: Reed ukázal, ze pro dostatečně velké D má každý graf maximálního stupně D neobsahující KD barevnost nejvýše D-1. Odhad na potřebnou hodnotu D v Reedove článku je poměrně slabý a autor tvrdí, ze přesnější analýzou jde podstatně vylepšit. Cílem práce by bylo nastudovat Reeduv důkaz a pokusit se o takovou podrobnější analýzu. Tato práce je vhodná pouze pro studenty s předchozí znalosti pravděpodobnostních metod.