Cvičení z Kombinatoriky a grafů I

Informace ke cvičením probíhajícím v učebně S6 ve středu od 14.00 a v učebně S7, v pátek od 10.40.

Tato cvičení jsou k přednášce Zdeňka Dvořáka (stránky přednášky).

K zápočtu je potřeba získat aspoň 2/3 bodů za domácí úkoly zadávané v průběhu semestru. Navíc je možno získat body aktivní účastí na cvičení. Úkoly můžete odevzdávat jak papírově, tak elektronicky na můj mail tereza-na-iuuk $\dot$ mff $\dot$ cuni $\dot$ cz. Elektronická řešení odevzdávejte nejlépe jako pdf (na sázení doporučuju LaTeX, ale klidně stačí i rukou psané a nascanované). Pokud máte k nějaké dotazy nebo máte zájem o konzultaci, napište mi mail.

Co bylo na cvičení

22./24.2. opakování kombinatoriky (počty podmnožin, funkcí, grafů)
29.2./2.3. odhad ${2n \choose n}$ a další odhady
7./9.3. princip inkluze a exkluze
14./16.3. vytvořující funkce, hlavně základní přiklady jak k posloupnosti najít vytvořující funkci
21./23.3. vytvořující funkce - pokračování, rekurence
28./30.4. dokončení vytvořujících funkcí, toky v sítích - Ford-Fulkersonův algoritmus
4./6.4. toky a řezy, toky v modifikovaných sítích, Hallova věta
11./13.4. dokončení toků a řezů, základní příklady na hranovou a vrcholovou souvislost
18./20.4. cvičení s Idou Kantorovou, příklady na souvislost
25./27.4. počítání koster
2./4.5. počítání dvěma způsoby
9./11.5. Ramseyovy věty
16./18.5. rektorský den/Ramseyovy věty - pokračování, předvedení domácích úkolů
23./25.5. dokončení Rams. vět, pravděpodobnostní metoda

Domácí úkoly

Byly zadány domácí úkoly celkem za 63 bodů. K získání zápočtu je tedy potřeba mít alespoň 42 bodů.

Třetí série

Třetí série nemá deadline. Do počtu bodů potřebného k zápočtu se počítají pouze první tři úlohy, ale možná se objeví ještě další úlohy, podle probrané látky.

Úkoly III. série jako pdf.

III.1 (3 body) Na přednášku přišlo 32 chlapců. Víme, že každý chlapec zná 5 z přítomných spolužaček a každá dívka zná 8 z přítomných spolužáků. Kolik je na přednášce děvčat? (Předpokládáme, že „znát se" je symetrická relace).

III.2 (3 body) Čísla 1,...,10 jsou uspořádána na kružnici. Ukažte, že pro libovolné uspořádání existují tři čísla, která v tomto uspořádání tvoří souvislý úsek a jejich součet je alespoň 17.

III.3 (3 body) Hrany úplného grafu na $n\geq 2$ vrcholech jsou obarveny dvěma barvami. Ukažte, že v grafu existuje jednobarevná kostra.

Bonusové příklady:

(nezvyšují počet bodů potřebných k zápočtu)

III.4 (3 body) Ukažte, že pro každé k, v libovolném obarvení hran úplného bipartitního grafu s nekonečně velkými partitami dvěma barvami existuje monochromatický úplný bipartitní podgraf, jehož jedna partita je nekonečná a druhá má velikost k.

III.5 (3 body) Vyvraťte nebo dokažte: Pro každé obarvení množiny mřížových bodů v rovině (bodů s celočíselnými souřadnicemi) pomocí 42 barev existují množiny 42 celých čísel $X$ a $Y$ takové, že všechny prvky $X\times Y$ jsou obarveny stejnou barvou.

III.6 (3 body) Do jednoho divadla si na představení zašlo N pánů a každý z nich nechal v šatně klobouk. Po skončení představení však roztržitá šatnářka vracela pánům klobouky zcela náhodně (všechna možná rozdělení klobouků jsou stejně pravděpodobná). Jaká je střední hodnota počtu pánů, kteří dostali zpátky svůj klobouk?

III.7 (3 body) Jaká je pravděpodobnost, že 1 a 2 jsou ve stejném cyklu náhodné permutace [n]?

III.8 (3 body) Jak se změní počet koster grafu $G$ s $n$ vrcholy a $m$ hranami, pokud podrozdělíme každou hranu jedním vrcholem (z každé hrany vznikne cesta o dvou hranách, získáme tedy graf $H$ s $n + m$ vrcholy a $2m$ hranami)?

Druhá série

Druhý deadline na domácí úkoly je 7.5. (pondělí). To té doby je možné odevzdávat všechny úlohy druhé série, tj. ty číslované II.n. Všechny úlohy druhé série budou zadány do konce dubna. Začátkem května bude zadána třetí série.

Úkoly II. série jako pdf.

II.1 (3 body) Pomocí Ford-Fulkersonova algoritmu najděte největší tok v síti na obrázku (kde čísla značí kapacity hran), a napište, jakou má hodnotu. Podrobně popište, jak algoritmus probíhal, jaké použil v jednotlivých krocích zlepšující cesty atd. Nakonec dokažte, že nalezený tok je skutečně největší tak, že najdete řez odpovídající kapacity.

II.2 (3 body) Mějme orientovaný graf $(V,E)$ , pro jehož každou hranu $e$ je dána kapacita $c(e)$ a pro každý vrchol $v$ je dán odtok, resp. přítok z resp. do daného vrcholu $d(v)$ . Cirkulace je funkce $f:E\rightarrow \mathbb{R}^+_0$ taková, že

pro každou hranu je $0\leq f(e)\leq c(e)$
pro každý vrchol je $\sum_{e \text{\ orientovan\'a\ do\ } v}f(e)-\sum_{e\text{\ orientovan\'a\ z\ } v}f(e)= d(v)$

Najděte algoritmus, který rozhodne zda cirkulace pro daný graf existuje a pokud ano, najde nějakou.

II.3 (3 body) Latinský obdélník je matice $m\times n$ , v jejímž každém řádku se vyskytují všechna čísla $1,\dots n$ a čísla v každém sloupci jsou navzájem různá. Ukažte, že pokud $m<n$ , k libovolnému latinskému obdélníku lze přidat řádek tak, aby vznikl obdélník $(m+1)\times n$ .

II.4 (3 body) Dokažte následující zobecnění Hallovy věty: Mějme množinový systém $(X,\mathcal{S})$ a přirozené číslo $k$ takové, že libovolný podsystém $\mathcal{T}\subseteq \mathcal{S}$ obsahuje alespoň $|\mathcal{T}|-k$ prvků. Potom po škrtnutí nejvýše $k$ množin má $\mathcal{S}$ systém různých reprezentantů.

II.5 (3 body) Dokažte, že každý souvislý regulární (tj. všechny jeho vrcholy mají stejný stupeň) bipartitní graf je 2-souvislý.

II.6 (3 body) Dokažte, že v každém 2-souvislém grafu $G\not= K_3$ existuje hrana $e$ taková, že graf vzniklý z $G$ kontrakcí $e$ je 2-souvislý.

II.7 (3 body) Dokažte nebo vyvraťte toto tvrzení: V každém 4-souvislém grafu $G\not= K_5$ existuje hrana $e$ taková, že graf vzniklý z $G$ kontrakcí $e$ je 4-souvislý.

II.8 (3 body) Dokažte, že každý kritický hranově 2-souvislý graf (tedy takový, že po odebrání jakékoliv hrany už nebude hranově 2-souvislý) má vrchol stupně 2.

II.9 (3 body) Podobným způsobem jako na cvičeních nalezněte rekurentní vzorec pro počet koster žebříku $L_n$ (viz obrázek).

První série

Správné řešení 1. série od Míšy Hubatové, kdyby jste měli ohledně řešení nějaké dotazy, napište mi.

První deadline na domácí úkoly je 10.4. (úterý po Velikonocích). To té doby je možné odevzdávat všechny úlohy první série, tj. ty číslované I.n. Úlohy budu zadávat postupně podle probrané látky, všechny úlohy první série budou zadány do konce března.

Úkoly I. série jako pdf.

I.1 (3 body) Kolika způsoby lze z $n$ -prvkové množiny $[n]$ vybrat tři podmnožiny $A$ , $B$ a $C$ tak, aby $A\cap B\cap C = \emptyset$ , $A\cap B\not= \emptyset$ a $A\cap C\not= \emptyset$ . Hint: Počítejte počet charakteristických funkcí $\chi_A$ , $\chi_B$ a $\chi_C$ pro $A,B$ a $C$ a zkoumejte trojice hodnot, které tyto funkce nabývají pro prvky $[n]$ .

I.2 (3 body) Dokažte, nejlépe úvahou: $\sum_{k=1}^{n}k^2{n\choose k} = n2^{n-1}+n(n-1)2^{n-2}$ .

I.3 (3 body) Seřaďte dle velikosti (pro hodně velké $n$ ) a zdůvodněte: $3^n, {2n \choose n}, {2n \choose 2}, \sum_{k=1}^{n}k!, n^n$ .

I.4 (3 body) Kolik je přirozených čísel menších než 1000, která jsou dělitelná 6,8 nebo 15?

I.5 (3 body) Kolik existuje permutací čísel 1,2,...,10, v nichž se žádné sudé číslo nezobrazí samo na sebe?

I.6 (3 body) Nalezněte vytvořující funkci (vyjádřenou bez pomoci nekonečné řady) k posloupnosti 1,0,3,2,5,4… (neboli $a_{2i}=2i+1$ a $a_{2i+1}=2i$ ).

I.7 (3 body) Najděte posloupnost s vytvořující funkcí $a(x) =\frac{1}{x^2/4-x+1}$ .

I.8 (3 body) Najděte vytvořující funkci a (nerekuretní) vzorec pro $a_n$ posloupnosti $a_0=0$ , $a_1=1$ a každý následující člen je aritmetickým průměrem předchozích dvou.

I.9 (3 body) U kulatého stolu sedí $n$ hostů. Chceme jim rozdat čtyři druhy koláčů tak, aby každý dostal jiný koláč než oba jeho sousedé. Kolika způsoby to můžeme udělat?

Body za aktivitu na cvičeních:

středa

		22.2.	29.2.	7.3.	14.3.
Aleš	Křivák	3
Ondřej	Papík			3
Tomáš	Pokorný	3
Petr	Sokola			2

pátek

		25.2.	2.3.	9.3.	16.3.
Jan	Brandejs				3
Vladimír	Dudr	3	3	2
Michaela	Hubatová				3
Anna	Chejnovská		3		3
David	Kuboň	3
Martin	Mečiar	3		2	6
Natália	Tyrpáková				3