Teorie grafů a algoritmy pro matematiky 1 (NDMA001) - cvičení

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

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

Stránky přednášky.
Podmínky získání zápočtu:
  • Získání alespoň 25 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ě.
  • Úč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   6   7a   7b   8   9   10a   10b   11   12   13   14   15   16   17   18   19   20a   20b   21   22   23   24   25   26   27   28   29   30   31   32   Součet   Zápočet 
 Maxim Dokonalý  3 2 2 2 4 2 1 1 4 2 1 1 1 2 4 2 3 2 3 1 2 2 2 3 4 3 2 3 2 3 5 2 2 3 4 85
 M. Žoldák  2 2
 Pepa T.  3 2 2 2 1 1 1 1 1 2 4 2 3 25 ANO
 Dominik Tělupil  3 2 1.5 1 0.5 1 2 1 1 1 4 2 3 2 25 ANO
 Pirastro  3 2 0 2 2 0.5 1 0 0.5 0 0.5 2 4 0 3 1 0 1 2 0.5 25 ANO
 Lex  2 2 2 2 1 1 0.5 2 4 0 3 1 2 2.5 25 ANO
 Milka  3 2 2 2 1 1 0.5 0.5 0.5 12.5
  • Zadání domácích úkolů: PDF (poslední aktualizace 20.5.2013)
Jednotlivá cvičení:
  • První cvičení (18.2.2013): Úvod, podmínky zápočtu, opakování teorie grafů. Probrány všechny příklady kromě příkladu 6b a části příkladu 4c. Seznam příkladů ze cvičení [PDF].
  • Druhé cvičení (25.2.2013): Toky a vlastnosti grafů. Probrány příklady 1a, 1b, 1d a 7. Seznam příkladů ze cvičení [PDF].
  • Třetí cvičení (4.3.2013): Toky v sítích. Probrány příklady 1a, 1b a 2. Ukázka sítě, na které Ford-Fulkersonův algoritmus selže. Časová analýza Edmonds-Karpova algoritmu. Seznam příkladů ze cvičení [PDF].
  • Čtvrté cvičení (11.3.2013): Aplikace Hallovy věty. Probrány příklady 1a, 1b, 2a, 2b, 2c a 3a. Algoritmus na hledání maximálního párování v bipartitním grafu. Seznam příkladů ze cvičení [PDF].
  • Páté cvičení (18.3.2013): Grafová souvislost. Na cvičení zaskakoval Josef Cibulka. Probrány příklady 1, 2, 3 a 4. Seznam příkladů ze cvičení [PDF].
  • Šesté cvičení (25.3.2013): Grafová souvislost podruhé. Probrány příklady 1, 2, a 3. Seznam příkladů ze cvičení [PDF].
  • Sedmé cvičení (1.4.2013): Cvičení se nekonalo (Velikonoce).
  • Osmé cvičení (8.4.2013): Rovinné grafy. Probrány příklady 1, 2, 3, 4 a 6 (s použitím Věty o 4 barvách). Seznam příkladů ze cvičení [PDF].
  • Deváté cvičení (15.4.2013): Grafová barevnost a vybíravost. Probrány příklady 1, 2, 3, a 6. Seznam příkladů ze cvičení [PDF].
  • Desáté cvičení (22.4.2013): Ramseyovy věty. Probrány příklady 1, 3, 5a a rovnosti ve 4. Příklad 2 zazněl na přednášce. Seznam příkladů ze cvičení [PDF].
  • Jedenácté cvičení (29.4.2013): Vytvořující funkce - úvod. Probrány příklady 1, 3a, 3b, 3c a 6. Seznam příkladů ze cvičení [PDF].
  • Dvanácté cvičení (6.5.2013): Vytvořující funkce - aplikace. Probrány příklady 1, 2, 3 a 4. Seznam příkladů ze cvičení [PDF].
  • Třinácté cvičení (13.5.2013): Konečné projektivní roviny. Probrány příklady 1, 2, 3 a 6. Algebraická konstrukce konečných projektivních rovin řádu mocniny prvočísla. Seznam příkladů ze cvičení [PDF].
  • Čtrnácté cvičení (20.5.2013): NP-úplnost a polynomiální převoditelnost. Probrány příklady 1b, 1c a 1d. Polynomiální převod problému nezávislé množiny na problém vrcholového pokrytí. Seznam příkladů ze cvičení [PDF].
Valid XHTML 1.0 Transitional