Cvičení NDMI011 KG1, v úterý 12:20, kruh 35

Pro získání zápočtu je nutné získat dostatek bodů - alespoň 80 bodů. Body lze získat následujícími způsoby:

• Za aktivitu na cvičení a řešení příkladů u tabule.
• Za řešení domácích úkolů zadávaných na jednotlivých cvičeních.
• Napsání zápočtových písemek - budou obsahovat úlohy podobné příkladům ze cvičení a na zkoušce, mělo by jít získat až 100 bodů.

Domácí úkoly budou vždy zadávány po sériích na téma, které jsme probírali na cvičeních. Na jejich vypracování budou většinou dva týdny. Úkoly se odevzdávají písemně na cvičeních. Na daném cvičení si pak ukážeme i jejich řešení. Navíc některé obtížnější úkoly mají otevřený časový limit.

Konzultační hodiny nevypisuji, ale lze si je domluvit po mailu. Ideální doba je například na konci cvičení.

Domácí úkoly

• Série 1: Opakování diskrétní matematiky (termín odevzdání 9.3.2010) PDF PS
• Série 2: Princip inkluze a exkluze (termín odevzdání 23.3.2010) PDF
• Série 3: Vytvořující funkce (termín odevzdání 6.4.2010) PDF PS
• Série 4: KPR, SRR a jiné TLA (termín odevzdání 27.4.2010) PDF PS
• Série 5: Latinské čtverce, Hallova věta, souvislost (termín odevzdání prodloužen do 18.5.2010) PDF PS
• Série 5: Latinské čtverce, Hallova věta, souvislost (termín odevzdání prodloužen do 1.9.2010) PDF PS

Co jsme dělali na cvičeních

• 23.02.2010 - úvodní cvičení; opakování diskrétní matematiky - permutace a počty zobrazení; kombinační čísla a rovnice pro jejich součty; dirichletův princip a příklady s přirozenými čísly; úvod ke grafům - základní pojmy; důkaz Turánovy věty pro trojúhelníky - každý graf bez trojúhelníku ma nejvýše n²/4 hran.
• 02.03.2010 - opakování diskrétní matematiky - grafy a jejich vlastnosti; barevnost rovinných a d-degenerovaných grafů; doplněk velikého rovinného grafu nemůže být rovinný; kritéria pro existenci Eulerovské tahu (uzavřeného/neuzavřeného); každý delta regulární graf obsahuje cestu délky alespoň delta a kružnici délky alespoň delta+1.
• 09.03.2010 - cvičil Honza Volec; princip inkluze a exkluze; počet uspořádání pohádkových bytostí (bez dvou stejného typu za sebou); počet čísel, která nejsou dělitelná 4, 5 a 6; počet surjektivních zobrazení a vztah s počtem ekvivalencí; doplňky kružnic a rovinnost (doplňky C₈, ani C₇ rovinné nejsou, naopak doplněk C₆ rovinný je).
• 16.03.2010 - úvod k vytvořujícím funkcím - nač jsou dobré a co vlastně znamenají; operace s vytvořujícími funkcemi - sčítání, násobení, různé substituce za x; odvozený zkráceného tvaru (bez mocninné řady) pro základní posloupnosti; vztah mezi vytvořující funkci posloupnosti a posloupnosti její částečných součtů; příklad s matfyzáckým obchodem - kolika způsoby lze koupit n kusů ovoce v obchodě, kde prodávají ananasy po dvou, banány po pěti a lze koupit nejvýše čtyři citróny a jedny datle; počet způsobů, jak napsat přirozené číslo jako součet přirozených čísel.
• 23.03.2010 - cvičil Honza Volec; pokračování vytvořujících funkcí; Catalanova čísla jako počet cest v mřížce, které nepřekročí diagonálu, počet binárních stromů a počet korektních uzávorkování; vytvořující funkce pro n² a pro její částečné součty.
• 30.03.2010 - pokračování vytvořujících funkcí; hledání n-tého členu posloupnosti zadaného rekurencí - s využítím rovnosti; počet způsobů, jak lze napsat přirozené číslo jako součet přirozených čísel; kombinatorický význam speciálních vytvořujících funkcí (počet dělitelů, počet monotonních součtů čísla n, ...).
• 06.04.2010 - vysvětlení úkolů na vytvořující funkce, aplikace zobecněné binomické věty; úvod do konečných projektivních rovin (axiomy, řád, motivace v projektivních rovinnách); dolní odhad na počet jedniček v 0-1 matici, ve které neexistují dva řádky a dva sloupce se čtyřmi jedničkami v průnicích.
• 13.04.2010 - první písemka PDF; Fanova rovina není dva obarvitelná.
• 20.04.2010 - latinské čtverce a Hallova věta; vztah latinských čtverců a konečných projektivních rovin - existuje KPR, právě když existuje n-1 navzájem ortogonálních latinských čtverců velikost n x n; vztah mezi ortogonálními latinskými a osvobozenými čtverci - jedna implikace; Hallova věta implikuje větu o harémech (každá z dívek chce jiný počet manželů); k-regulární bipartitní graf je 1-faktorizovatelný; graf s levou partitou stupně alespoň k a pravou stupně nejvýše k má párování nasycující levou partitu; matice 0-1 jako matice incidence partit bipartitního grafu.
• 27.04.2010 - vysvětlení úkolů na KPR a SRR; aplikace Hallovy věty; trik s doplňkem na partitě - pro bipartitní graf se stejně velkými partitami je splnění Hallových podmínek pro levou a pravou partitu ekvivalentní (a i pro všechny vrcholy dohromady); doplňování latinských obdélníků na čtverce pomocí párování; zesílení Halla - existuje alespoň m! různých SRR, pokud navíc k Hallově podmínce každá množina obsahuje alespoň m prvků (a množin je alespoň m), spolu s důsledkem, že existuje alespoň n!(n-1)!...1! různých latinských čtverců; původní Hallova aplikace na cosety z teorie grup - pro množinu a její dvě rozdělení X a Y (pomocí n disjunktních množin velikosti k), potom existuje "spolecný" systém různých reprezentantu pro rozklady X a Y; každý rovinný graf má orientaci s výstupním stupněm nejvýše 3 - překvapivý důsledek Hallovy věty.
• 04.05.2010 - párování v obecných grafech, toky v síti a k-souvislost; 2k-regulární grafy (ne nutně bipartitní) jsou 2-faktorizovatelné (lze je rozložit na disjunktní 2-faktory, což jsou disjunktní sjednocení kružnic pokrývajících celý graf); tancování na večírku - úplný bipartitní graf Kn,n má n! perfektních párování, úplný graf K_2n má (2n-1)(2n-3)...1=(2n-1)!! perfektních párování; jak vypadá symetrická difference dvou párování (hrany, které jsou právě v jednom z nich) - je to podgraf složený z disjunktních kružnic, cest a izolovaných vrcholů; důsledek Bergeho věta - párování je maximální, právě když neexistuje střídavá cesta, jejím přehozením by se párování zvětšilo; toky v síti - definice s motivací, spolu s příkladem; v k-rozměrné hyperkrychli existuje tok velikosti k mezi vrcholem 0..0 a 1..1; souvislost a Mengerovy věty; z ušatého lemmatu víme, že ve 2-souvislém grafu existuje pro dva libovolné vrcholy kružnice, která jimi prochází; platí i zobecnění, v k-souvislém grafu pro libovolných k vrcholů existuje kružnice, která jimi prochází; trik s podrozdělením hrany - ve 2-souvislém grafu existuje pro libovolný vrchol a hranu kružnice, která jimi prochází; trik s přidáním dvou vrcholů a převodem na Mengerovu větu - v k-souvislém grafu existují pro dvě libovolné k-tice vrcholů A a B k vrcholově disjunktních cest, které propojují vrcholy z A s vrcholy z B.
• 11.05.2010 - psala se druhá písemka.