Kombinatorika a grafy - cvičení

Zde se průběžně budou objevovat nějaké informace ke cvičením (pondělí, 9:00 v S7). Najdete tu příklady k cvičením.

Pokud hledáte kontakt na mě, tak se podívejte na moji domovskou stránku.

Náhradní písemka

Kdo ještě nemá dostatek bodů na zápočet, může body získat na náhradní zápočtové písemce (za obě předchozí písemky) v úterý 29. 5. v učebně S8 od 13:00.

Body získané za docházku, aktivitu a DÚ se budou plně započítávat. Body za předchozí písemky se budou započítávat částečně. (Také je možné např. ponechat si všechny body z první písemky a opravovat pouze druhou písemku.)

DÚ 3

Kdo má zájem ještě nahnat nějaké body před náhradní písemkou, popř. se (v jednom případě) náhradní písemce zcela vyhnout, může získat nějaké body připomenutím si generujících/vytvořujících funkcí a vyřešením následujícího domácího úkolu:

Určete vzorec pro n-tý člen rekurentně zadané posloupnosti.

a) a0=1, a1=1, an+2= an+1 + 6an + 2n [5 bodů]

b) a0=1, a1=1, an+2= an+1 + 6an + n [7 bodů]

Termín: 17. 6. 2018

Výsledky 2. písemky a celkové bodování

Bodování už obsahuje body za 2. písemku a DÚ2. Kdo má 100 a více bodů, získává zápočet. Instrukce pro ostatní doplním dnes (21. května) nebo zítra.

Je více než vítané, pokud se se mnou na někdy domluvíte, abyste se zašli podívat na svoji opravenou písemku. Uvidíte chyby, které jste dělali.

A ještě poznámka k úloze 5b: jednalo se o trochu těžší úlohu za body navíc. Většinou jste správně určili hranovou souvislost, ale těžištěm úlohy bylo dokázat, že hranová souvislost není menší. Předpokládal jsem, že se to několika z Vás podaří, ale nakonec se to nepodařilo pořádně nikomu. Proto jsou za ni vesměs skromné bodové úděly.

Druhá písemka

Počítejte s druhou písemkou 21. května. Písemka bude na celé cvičení, za 90 bodů.

DÚ 2

Nabízím druhý (dobrovolný) domácí úkol. Je za něj možné získat 7 bodů. Nalezněte všechny grafy které mají skóre (6,4,4,3,3,3,3) a nejsou vrcholově 3-souvislé. U každého určete jeho hranovou souvislost a zdali je rovinný. Všechny kroky podrobně zdůvodněte. Termín odevzdání: 21. května (před písemkou).

Dobrovolný DÚ 1

Nabízím první DÚ. Není povinný, ale můžete si jím vylepšit body po první písemce. Všechny kroky důkladně vysvětlujte. Termín odevzdání: 30. dubna, 9:00. (Úkol je též možno poslat elektronicky.)

Určete počet koster následujících grafů:

(a) Graf G získáme tak, že uvážíme kružnici Cm a na ní dvě různé hrany e a f. K hraně e přilepíme úplný graf Kn a k hraně f přilepíme úplný graf Kp. (Takový graf není určen jednoznačně. Pokud odpověď závisí na vzájemné poloze hran e a f tak tuto závislost popište i ve svém řešení.) [5 bodů]

(b) Graf H získáme tak, že uvážíme disjunktní sjednocení nezávislé množiny Im a úplného grafu Kn. Následně každý vrchol Im spojíme hranou s každým vrcholem Kn. (Jinými slovy výsledný graf získáme z úplného bipartitního grafu Km, n tak, že na části s n vrcholy navíc utvoříme úplný graf.) [5 bodů]

Výsledky 1. písemky

Výsledky 1. písemky naleznete zde. Zároveň tam naleznete i bodování za aktivitu k datu 26. 3.

První písemka

Počítejte s první písemkou 26. března. Bude se jednat o kratší písemku na 60 minut a za 60 bodů.

Podmínky k zápočtu

Pro získání zápočtu je potřeba dosáhnout 100 bodů. Základem je úspěšné absolvování dvou písemek, první písemka bude na cca 60 minut za 60 bodů; druhá písemka bude na celé cvičení za 90 bodů. Dále je možné získat nějaké body navíc za docházku (8 bodů), aktivitu během cvičení (není omezeno, čekejte tak kolem 12-15 bodů pro aktivnější), příležitostné domácí úkoly. V případě neúspěchu při řešení písemek bude náhradní možnost (ale doporučuji se připravit už napoprvé, dříve budete moci ke zkoušce).

Příklady z cvičení

Zde se budou objevovat příklady z cvičení ve formátu .pdf. Jsou vytvořeny pomocí aplikace sbírka příkladů. V této sbírce naleznete i řešení některých příkladů.

19. 2.: zadání 1. série (verze pro tisk) [Odhady faktoriálů, kombinačních čísel apod.]

26. 2.: zadání 2. série (verze pro tisk). [Generující (vytvořující) funkce.]

5. 3.: zadání 3. série (verze pro tisk). [Rekurentní posloupností.]

12. 3.: Příklady z minula.

19. 3.: zadání 4. série (verze pro tisk). [Konečné projektivní roviny.]

26. 3.: Byla písemka (60 minut); zadání 5. série (verze pro tisk). [Latinské čtverce.]

9. 4.: zadání 6. série (verze pro tisk). [Počítání dvěma způsoby a počet koster.]

16. 4. Příklady z minula + počet koster Kn procházejících danou hranou.

23. 4.: zadání 7. série (verze pro tisk), cvičení s P. Korcsokem. [Toky v sítích, párování.]

30. 4.: zadání 8. série (verze pro tisk). [Systémy různých reprezentantů, k-souvislost.]

7. 5.: zadání 9. série (verze pro tisk), cvičení s J. Fialou. [k-souvislost, pokračování.]

14. 5.: zadání 10. série (verze pro tisk). [Ramseyova teorie.]