Základy kombinatoriky a teorie grafů (NMIN331) - cvičení


Cvičení probíhá každé pondělí od 12:20 v učebně K8.

Cvičení povede Martin Balko. E-mail cvičícího: balko (AT) kam.mff.cuni.cz

Stránky přednášejících: Jan Kratochvíl a Tomáš Gavenčiak.


Podmínky získání zápočtu:
  • Získání alespoň 20 bodů.
  • V průběhu semestru zadám několik sérií příkladů, kde každý příklad bude ohodnocen určitým počtem bodů podle obtížnosti. Všechny úlohy (domácí i ty řešené na cvičeních) budou dostupné zde na webu.
  • Termín pro vyřešení a sepsání úkolů bude zhruba do konce semestru, ale vyplatí se řešení odevzdávat průběžně.
  • Příklady je možné odevzdávat opakovaně, vždy se počítá nejlepší dosažený výsledek.
  • Účast na cvičeních je nepovinná.
  • Z důvodu ochrany osobních údajů u prvních odevzdaných řešení napište kromě jména i přezdívku, pod kterou chcete mít své body zveřejněny na webu. U dalších řešení už stačí psát buď jméno, nebo přezdívku. Pokud jste první sérii úkolů odevzdali jen pod svým jménem, bude uveřejněno na webu. Pokud Vám to nevyhovuje, napište mi email s přezdívkou a já to změním.
  • Aktuální seznam bodů:
Přezdívka:  1   2   3   4   5   6a   6b   7   8   9   10   11a   11b   12   13a   13b   14   Součet   Zápočet 
  Maxim Dokonalý   3 2 3 2 3 2 3 2 3 3 3 2 2 2 3 4 4 46 ---
  Falko   3 1 2.5 2 3 1.5 2 1.5 1.5 3 4 25 ANO
  ŠX64   3 2 3 2 3 2 3 1.5 3 3 2 2 2 31.5 ANO
  2^(6k)-1   3 2 3 8
  Gamba   3 2 3 2 3 2 2 2 1.5 20.5 ANO
  DM K   3 2 2 3 2 3 1 3 19
 Fakir  3 2 3 2 2 2 2 1 2 2.5 21.5 ANO
  KTBBTK   3 2 3 2 3 2 3 2 20 ANO
   
  • Zadání domácích úkolů: [PDF] (poslední aktualizace 6.5.2018)

Jednotlivá cvičení:
  • První cvičení (19.2.2018): Úvod, podmínky zápočtu, opakování z teorie grafů. Probrány příklady 1, 2, 3, 4, 5, 7 a 8a. Seznam příkladů ze cvičení [PDF].
  • Druhé cvičení (26.2.2018): Opakování z teorie grafů podruhé. Probrány příklady 1, 3, 4, 6a a 6b. Seznam příkladů ze cvičení [PDF].
  • Třetí cvičení, 1. část (5.3.2018): Vytvořující funkce - úvod. Probrány příklady 1, 2, 3a, 3b, 3d, 4a, 5 a 6. Seznam příkladů ze cvičení [PDF].
  • Třetí cvičení, 2. část (5.3.2018): Vytvořující funkce - aplikace. Probrány příklady 2, 3, 4 a 5. Seznam příkladů ze cvičení [PDF].
  • Čtvrté cvičení (12.3.2018): Cvičení nahrazeno přednáškou (Jan Kratochvíl).
  • Páté cvičení (19.3.2018): Cvičení nahrazeno přednáškou (Tomáš Gavenčiak).
  • Šesté cvičení (26.3.2018): Grafová souvislost. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].
  • Sedmé cvičení (2.4.2018): Cvičení se nekoná (Velikonoce).
  • Osmé cvičení (9.4.2018): Rovinné grafy. Probrány příklady 1b, 2, 3, 4 a 5. Příklad 1a zazněl na přednášce. Seznam příkladů ze cvičení [PDF].
  • Deváté cvičení (16.4.2018): Ušaté lemma a bloková struktura. Probrány příklady 1, 2, 3 a dokázáno, že v každém rovinném nakreslení vrcholově 2-souvislého rovinného grafu jsou všechny stěny grafovými kružnicemi. Seznam příkladů ze cvičení [PDF].
  • Desáté cvičení (23.4.2018): Hamiltonovské kružnice. Probrány příklady 1, 2, 3, 4b, 5a a 5b. Příklad 4a zazněl na přednášce. Seznam příkladů ze cvičení [PDF].
  • Jedenácté cvičení (30.4.2018): Cvičení nahrazeno přednáškou (Jan Kratochvíl).
  • Dvanácté cvičení, 1. část (7.5.2018): Ramseyova teorie. Probrány příklady 1, 2, a 3. Seznam příkladů ze cvičení [PDF].
  • Dvanácté cvičení, 2. část (7.5.2018): Ramseyova teorie. Probrány příklady 5a, 5c a 7 a ukázán důkaz tvrzení z příkladu 3a bez indukce. Seznam příkladů ze cvičení [PDF].
  • Třinácté cvičení (14.5.2018): Turingovy stroje. Probrány příklady 1, 2, 3, 5 a v rychlosti vysvětlen příklad 6. Seznam příkladů ze cvičení [PDF].
  • Čtrnácté cvičení (21.5.2018): Bude doplněno.

Valid XHTML 1.0 Transitional