Druhá sada zadání

Napsat referát z předmětu Diskrétní matematika musí každý student sám, žádná spolupráce na textu referátu není dovolena. Je však povoleno o zadání referátu volně diskutovat se spolužáky i na cvičeních. 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 e-mailem nebo na papíře příslušnému vyučujícímu (kontakt je uveden u každého zadání). Cvičící vás může vyzvat k 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 psáno 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.

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

1. Souvislé grafy

Referát vypracovaný podle pokynů posílejte na adresu: Pavla<tečka>Kabelíková<zavináč>vsb<tečka>cz.

Dokažte, že každý graf G na 2δ(G)+1 vrcholech je souvislý pro δ(G) ≥ 1.

2. Eulerovské tahy

Referát vypracovaný podle pokynů posílejte na adresu: Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Máme dán souvislý graf G na n vrcholech ve kterém je právě 2k vrcholů lichého stupně. Dokažte, že G je možno nakreslit k otevřenými tahy.

3. Hamiltonovský cyklus

Referát vypracovaný podle pokynů posílejte na adresu: Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Nechť V(G) grafu G je množina všech dvouprvkových podmnožin množiny [1,5] a nechť hrana XY ∈ E(G) právě tehdy, když jsou dvouprvkové podmnožiny X,Y disjunktní (X ∩ Y = ∅). Je graf G hamiltonovský? Své tvrzení dokažte.

4. Strom a les

Referát vypracovaný podle pokynů posílejte na adresu: Tomáš<tečka>Kupka<tečka>fei<zavináč>vsb<tečka>cz.

a) Dokažte, že acyklický graf s n vrcholy a m hranami je nesouvislý právě tehdy, když m<n-1.
b) Jak zjistíme počet komponent acyklického nesouvislého grafu, když známe pouze počet jeho vrcholů a hran?
c) Kolik vznikne komponent, jestliže ze stromu odstraníme vrchol stupně k. Dokažte.

5. Integrovaný dopravní systém

Referát vypracovaný podle pokynů posílejte na adresu: Tomáš<tečka>Kupka<tečka>fei<zavináč>vsb<tečka>cz.

K řešení vám může posloužit jeden z možných návrhů integrovaného systému na obrázku.

Problém však řešte pro obecný integrovaný systém, který má stejnou strukturu, jako uvedený systém. Tedy IS je popsán jedním multigrafem, v kterém jsou zaznačeny jednotlivé linky, a jednoduchým grafem s ohodnocenými hranami, který popisuje časovou vzdálenost mezi zastávkami. Mějme k dispozici funkci: waitConnection(number, time, station) ... vrátí dobu čekání na spoj number od doby time v zastávce station.
Funkci waitConnection nemusíte implementovat, předpokládá se, že ta je k dispozici.

Nejdůležitější součástí vašeho řešení je slovní popis a rozbor činnosti vašeho algoritmu. 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.

6. Délka cyklu

Referát vypracovaný podle pokynů posílejte na adresu: Pavla<tečka>Kabelíková<zavináč>vsb<tečka>cz.

Dokažte, že každý graf G obsahuje cyklus délky alespoň δ(G)+1 pro δ(G) ≥2.

Návod: Ukažte, že každý graf G obsahuje cestu délky δ(G). Dále využijte pojmu nejdelší cesta v grafu, má totiž jednu, pro nás, pěknou vlastnost, týkající se jejich koncových vrcholů.

7. Třipravidelné grafy

Referát vypracovaný podle pokynů posílejte na adresu: Michael<tečka>Kubesa<zavináč>vsb<tečka>cz.

Nalezněte 3-pravidelné (všechny vrcholy jsou stupně 3), k-souvislé a hranově k'-souvislé grafy na co nejmenším počtu vrcholů tak, aby platilo pro maximální k a maximální k':

• (a) k=k'=3,
• (b) k=2, k'=3,
• (c) k=1, k'=3,
• (d) k=k'=2,
• (e) k=1, k'=2.

Poznámka: Nalezený graf G musí splňovat OBĚ podmínky, jak pro k, tak pro k'.

8. Délka nejkratšího cyklu

Referát vypracovaný podle pokynů posílejte na adresu: Michael<tečka>Kubesa<zavináč>vsb<tečka>cz.

Nechť V(G) grafu G je množina všech dvouprvkových podmnožin množiny [1,5] a nechť hrana XY ∈ E(G) právě tehdy, když jsou dvouprvkové podmnožiny X,Y disjunktní (X ∩ Y = ∅). Jakou délku má nejkratší cyklus v grafu G? Své tvrzení dokažte.

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.