Homepage
Curriculum vitae
Publikace
Výuka
Kontakt
   

Referáty z Diskrétní matematiky ZS 2005/2006

Toto není stránka aktuálního akademického roku.

Druhá sada zadání

Napsat referát z předmětu Diskrétní matematika musí každý student sám, žádná spolupráce na výsledném textu referátu není dovolena. Je však povoleno o zadání referátu volně diskutovat se spolužáky i na cvičeních, vše kromě samotného zpracování. Hodnocení referátů je buď 0 nebo 10 bodů, tj. stylem ANO/NE. V případě mimořádně kvalitního referátu lze udělit i 20 bodů. Referát odevzdáváte vyhlašovateli tématu e-mailem nebo na papíře. Cvičící vás také může vyzvat k ústnímu přednesení vašeho referátu během cvičení.

Každý referát vypracujete formou odborného článku, tj. musí mít nadpis, jméno, abstrakt a přehledné členění na sekce, to vše psané na počítači v rozsahu asi 2 až 5 stran A4. Abstrakt je zhruba jeden odstavec shrnující, o čem referát je a co je hlavním přínosem vaší práce, zahrnuje i podstatu zadání. Zadání referátu nekopírujte do výsledného textu, ale opište vlastními slovy v úvodu, popište co jste vlastně řešili. Pro ukázku správného stylu uvádíme dva referáty DIM z roku 2003: 1. referát a 2. referát s extra body.

Preferujeme odevzdávání referátů e-mailem ve formátu PS či PDF, přičemž v těle e-mailu musíte uvést studentské číslo a PDF soubor přikládáte nesbalený. (Pokud PDF zatím neumíte vytvářet, pořiďte si OpenOffice nebo pdfTeX, obojí je zdarma...) Výjimečně lze přijmout i jiné otevřené formáty, jako HTML. Export v těchto formátech však musí být proveden tak, aby byl výsledek přenositelný, mimo jiné nebudou přijaty žádné referáty obsahující soubory nebo vsuvky ve formátu WMF(!) nebo používající špatně převedenou diakritiku ve jménech souborů.

Následují zadání první sady samostatných referátů pro předmět Diskrétní matematika. K vybranému tématu se přihlásíte v KatISu (až do nastavených limitů).

1. Grafy, které mají m hran

Referát vypracovaný podle pokynů posílejte na adresu: .

Sestavte algoritmus, který ve vhodné reprezentaci vygeneruje všechny grafy na n vrcholech, které mají m hran.
Součástí práce má být zdůvodnění správnosti algoritmu.

Programovací jazyk je libovolný, nejdůležitější součástí vašeho řešení je slovní popis a rozbor činnosti vašeho algoritmu, zahrnující i zdůvodnění jeho správnosti, a komentovaný výpis hlavních částí vašeho programu. (Do komentovaného výpisu programu zahrňte jen skutečně výkonné části kódu, není důležité, jak ošetřujete vstup a výstup a jaké máte knihovny.) Mějte na paměti, že výpis programu je jen přílohou, klíčový je slovní popis a rozbor.

 

2. Grafy se stupňovou posloupností

Referát vypracovaný podle pokynů posílejte na adresu: .

Sestavte algoritmus, který ve vhodné reprezentaci sestaví alespoň jeden (lépe však všechny) grafy se zadanou konečnou stupňovou posloupností.
Součástí práce má být zdůvodnění správnosti algoritmu.

Programovací jazyk je libovolný, nejdůležitější součástí vašeho řešení je slovní popis a rozbor činnosti vašeho algoritmu, zahrnující i zdůvodnění jeho správnosti, a komentovaný výpis hlavních částí vašeho programu. (Do komentovaného výpisu programu zahrňte jen skutečně výkonné části kódu, není důležité, jak ošetřujete vstup a výstup a jaké máte knihovny.) Mějte na paměti, že výpis programu je jen přílohou, klíčový je slovní popis a rozbor.

 

3. Vrcholově magické grafy

Referát vypracovaný podle pokynů posílejte na adresu: .

Vrcholově magické totální ohodnocení grafu je bijektivní zobrazení λ, které v vrcholům a e hranám grafu přiřadí celé číslo z množiny { 1, 2, ..., e+v} tak, aby

wλ(x) = λ(x) + Σy ∈ N(x) λ(xy)
bylo rovno stejné konstantě h pro všechny vrcholy x grafu. Symbolem N(x) rozumíme množinu všech vrcholů sousedních s vrcholem x. Konstanta h se nazývá magická konstanta grafu při ohodnocení λ.

Sestavte algoritmus, který pro daný graf G a číslo h spočítá kolik různých vrcholově magických totálních ohodnocení s magickou konstantou h graf G má.
Součástí práce má být zdůvodnění správnosti algoritmu.

Programovací jazyk je libovolný, nejdůležitější součástí vašeho řešení je slovní popis a rozbor činnosti vašeho algoritmu, zahrnující i zdůvodnění jeho správnosti, a komentovaný výpis hlavních částí vašeho programu. (Do komentovaného výpisu programu zahrňte jen skutečně výkonné části kódu, není důležité, jak ošetřujete vstup a výstup a jaké máte knihovny.) Mějte na paměti, že výpis programu je jen přílohou, klíčový je slovní popis a rozbor.

Poznámka

Není znám jiný algoritmus, než "vyzkoušet všechny možnosti". Nicméně existuje celá řada omezení, která je do algoritmu možno zahrnout a výrazně urychlit běh algoritmu. Například pro C5 jistě nemůže být magická konstanta 1 ani 1000.
Pro kontrolu vyzkoušejte Váš algoritmus pro grafy K5, C5, P5 a K1,5.

 

4. Hranově magické grafy

Referát vypracovaný podle pokynů posílejte na adresu: .

Hranově magické totální ohodnocení grafu je bijektivní zobrazení λ, které v vrcholům a e hranám grafu přiřadí celé číslo z množiny { 1, 2, ..., e+v} tak, aby

wλ(xy) = λ(x) + λ(xy) + λ(y)
bylo rovno stejné konstantě k pro všechny hrany xy grafu. Konstanta k se nazývá magická konstanta grafu při ohodnocení λ.

Sestavte algoritmus, který pro daný graf G a číslo k spočítá kolik různých hranově magických totálních ohodnocení s magickou konstantou k graf G má.
Součástí práce má být zdůvodnění správnosti algoritmu.

Programovací jazyk je libovolný, nejdůležitější součástí vašeho řešení je slovní popis a rozbor činnosti vašeho algoritmu, zahrnující i zdůvodnění jeho správnosti, a komentovaný výpis hlavních částí vašeho programu. (Do komentovaného výpisu programu zahrňte jen skutečně výkonné části kódu, není důležité, jak ošetřujete vstup a výstup a jaké máte knihovny.) Mějte na paměti, že výpis programu je jen přílohou, klíčový je slovní popis a rozbor.

Poznámka

Není znám jiný algoritmus, než "vyzkoušet všechny možnosti". Nicméně existuje celá řada omezení, která je do algoritmu možno zahrnout a výrazně urychlit běh algoritmu. Například pro C5 jistě nemůže být magická konstanta 1 ani 1000. Pro kontrolu vyzkoušejte Váš algoritmus pro grafy K5, C5, P5 a K1,5.

 

5. Orákulum I

Referát vypracovaný podle pokynů posílejte na adresu: .

Předpokládejme, že máme k dispozici orákulum, kterému předložíme graf G a číslo k. Orákulum nám řekne "ano", pokud v grafu G existuje nějaká nezávislá množina vrcholů o velikosti k a "ne" v opačném případě.

Sestavte a podrobně slovně popište algoritmus, který s využitím orákula najde největší nezávislou množinu vrcholů daného grafu G. Podmínkou je, aby celkový počet kroků (jednu otázku položenou orákulu považujeme za jeden krok) provedených algoritmem byl polynomiální vzhledem k velikosti grafu a stupeň tohoto polynomu byl co nejmenší.

Součástí práce musí být zdůvodnění správnosti algoritmu i zdůvodnění, že počet kroků algoritmu lze omezit vzhledem k velikosti grafu (počtu vrcholů n a počtu hran m) polynomiální funkcí.

6. Orákulum II

Referát vypracovaný podle pokynů posílejte na adresu: .

Předpokládejme, že máme k dispozici orákulum, kterému předložíme graf G. Orákulum nám řekne, jaká je velikost největší nezávislé množiny hran v grafu G. Nezávislá množina hran je taková množina hran, ve které žádné dvě hrany nesousedí (tedy nemají společný vrchol).

Sestavte a podrobně slovně popište algoritmus, který s využitím orákula najde největší nezávislou množinu hran daného grafu G. Podmínkou je, aby celkový počet kroků (jednu otázku položenou orákulu považujeme za jeden krok) provedených algoritmem byl polynomiální vzhledem k velikosti grafu a stupeň tohoto polynomu byl co nejmenší.

Součástí práce musí být zdůvodnění správnosti algoritmu i zdůvodnění, že počet kroků algoritmu lze omezit vzhledem k velikosti grafu (počtu vrcholů n a počtu hran m) polynomiální funkcí.

7. Isomorfismus grafů

Referát vypracovaný podle pokynů posílejte na adresu: .

Sestavte a ve vhodném programovacím jazyku implementujte heuristický algoritmus (nebude používat hrubou sílu), který rozhodne zda jsou dva grafy G1 a G2 izomorfní. Pokud ano, najděte všechna bijektivní zobrazení f z V(G1) do V(G2) taková, že každá dvojice vrcholů u, v z V(G1) je spojená hranou v G1 právě tehdy, když je dvojice f(u), f(v) z G2 spojena hranou v G2.

Program bude umožňovat export dat z textového souboru, který bude reprezentovat graf pomocí matice sousednosti tak, že jednotlivé prvky každého řádku matice budou od sebe odděleny čárkou a řádky matice středníkem.

 

8. Kostry grafů

Referát vypracovaný podle pokynů posílejte na adresu: .

Sestavte a ve vhodném programovacím jazyku implementujte heuristický algoritmus (nebude používat hrubou sílu), který pro ohodnocený graf G o m hranách zjistí počet všech neizomorfních koster v grafu G s cenou i, pro všechna i, pro která existuje alespoň jedna neizomorfní kostra. Předpokládáme, že každá hrana i z E(G), pro i z množiny 1, 2, ..., m ohodnocena přirozeným číslem ci,

Program bude umožňovat export dat z textového souboru, který bude reprezentovat graf pomocí matice sousednosti tak, že jednotlivé prvky každého řádku matice budou od sebe odděleny čárkou a řádky matice středníkem.

 

9. Dobré hranové barvení

Referát vypracovaný podle pokynů posílejte na adresu: .

Najděte algoritmus dobrého hranového barvení úplného bipartitního grafu Km,n takový, že použijete nejvýše Δ(Km,n) barev, kde Δ(G) je nejvyšší stupeň vrcholu v grafu G.
Dobré hranové barvení grafu m barvami znamená, že každá hrana grafu je obarvena právě jednou z m barev a žádný vrchol není incidentní s dvěma či více hranami, které jsou obarveny toutéž barvou.

Pozor! Přidané vysvětlení:

Programovací jazyk je libovolný, nejdůležitější součástí vašeho řešení je slovní popis a rozbor činnosti vašeho algoritmu, zahrnující i zdůvodnění jeho správnosti, a komentovaný výpis hlavních částí vašeho programu. (Do komentovaného výpisu programu zahrňte jen skutečně výkonné části kódu, není důležité, jak ošetřujete vstup a výstup a jaké máte knihovny.) Mějte na paměti, že výpis programu je jen přílohou, klíčový je slovní popis a rozbor.

 

10. Komponenty stromu

Referát vypracovaný podle pokynů posílejte na adresu: .

Nechť T je strom na alespoň 2 vrcholech a v je jeho libovolný vrchol stupně k. Dokažte, že platí ω(T-v) = k.
T-v je strom T, ze kterého je vynechaný vrchol v a ω(G) je počet komponent grafu G.

Pozor! Přidané vysvětlení:

Tvrzení samo o sobě není obtížné. Smyslem tohoto referátu je vypracovat korektní důkaz. Vycházet můžete z pojmů probraných ve skriptech a na přednášce.

 

11. Chybný důkaz

Referát vypracovaný podle pokynů posílejte na adresu: .

Věta o čtyřech barvách zní:

Každý planární graf je dobře vrcholově obarvitelný nejvýše čtyřmi barvami.

Ukažme si její důkaz. :-)

Důkaz: Nechť je na dobré vrcholové obarvení grafu G třeba alespoň 5 barev. Potom ovšem G obsahuje jako svůj podgraf K5. Dle Kuratowského věty však takový graf není planární.
Tento důkaz jistě není v pořádku, že?! Nalezněte chybu! Umíte najít graf, který neobsahuje K5 jako svůj podgraf, a přitom je třeba na jeho dobré vrcholové obarvení alespoň 5 barev?
Dobré vrcholové barvení grafu m barvami znamená, že každý vrchol grafu je obarven právě jednou z m barev a žádné dva sousední vrcholy nejsou obarveny toutéž barvou.

 

12. Večírek

Referát vypracovaný podle pokynů posílejte na adresu: .

Na večírku je alespoň 6 osob. Někteří se znají a někteří ne.
(POZOR, relace "znát se" je zde chápána jako SYMETRICKÁ relace.)
Dokažte, že mezi těmito osobami určitě existuje trojice osob taková, že se buď všichni tři navzájem znají a nebo se všichni tři (po dvojicích) navzájem neznají.

 

13. Stromy jako bipartitní grafy

Referát vypracovaný podle pokynů posílejte na adresu: .

Dokažte, že každý strom je bipartitní graf, přičemž platí, že graf je bipartitní právě tehdy, když je dobře vrcholově obarvitelný nejvýše dvěma barvami.

 

Mnoho zdaru při řešení samostatných referátů!

Poznámka

Pokud najdete v textu zadání chybu, dejte mi, prosím, vědět. Pokusím se chyby co nejdříve opravit.

Toto není stránka aktuálního akademického roku.

Zpět na stránku předmětu Diskrétní matematika.

email
kancelář EA536, tel. 597 325 972		 Upraveno: 29.12.2011