Kombinatorika a grafy I – cvičení

V LS 2009/2010 vedu cvičení z Kombinatoriky a grafů I [NDMI011] ke své přednášce. Cvičení se koná každé pondělí od 10:40 v S7.

Zápočet si lze vysloužit za získání alespoň 100 bodů za domácí úkoly (sepsány níže). Každý domácí úkol lze řešit 14 dní od zadání za plný počet bodů, pak na cvičení povím nápovědu a bude možné získat poloviční počet bodů.

Co jsme dělali

datum	co se cvičilo
22. 2.	Opakování diskrétky: Kdy je úplný bipartitní graf rovinný? Doplněk rovinného grafu na 11 a více vrcholech nemůže být rovinný. Počítání s kombinačními čísly a binomickou větou.
1. 3.	Rozcvička na symptotické porovnávání funkcí: C(2n,n), C(2n,n-1), C(2n,n+1), C(2n,10), n^sqrt(n), (sqrt(n))ⁿ, n!. Odhady funkce π(n) (počet prvočísel mezi 1 a n) pomocí kombinačních čísel: Součin všech prvočísel mezi n a 2n dělí C(2n,n), takže je menší než 4ⁿ. Z toho plyne, že počet těchto prvočísel je nejvýše d*n/log n, kde d je nějaká konstanta. Pár grafů: vyvážené a skoro vyvážené orientace, v grafu s minimálním stupněm δ existuje cesta délky δ.
8. 3.	Princip inkluze a exkluze: Čísla od 1 do 1000, která nejsou dělitelná 6, 7, ani 8. Permutace písmen A až P bez vybraných podposloupností PONK, DOBA, COP. Permutace s právě K pevnými body. Různé rekurence pro šatnářčina čísla.
15. 3.	Jak vyrobit z posloupnosti vytvořující funkci a naopak. Jaké koeficienty má polynom (1+x)(1+x²)(1+x⁴)…(1+x^{2^k})? Zobecněná kombinační čísla. Dláždění dominovými kostkami. Variace na pana Fibonacciho.
22. 3.	Hrátky s lineárními rekurencemi. Jakou kombinatorickou identitu se dozvíme z rovnosti vytvořujících funkcí 1/(1-x) = (1/(1-x)^1/2)²?
29. 3.	Rekurence g₀=1, g_n = 1g_n-1 + 2g_n-2 + … n*g₀, řešení pomocí násobení vytvořujících funkcí nebo dvojí diferencí. Catalanovské struktury: stromy, mřížové cesty, závorkování, stavby z mincí …
5. 4.	Ēostre, Paasfees, Великден, Ülestõusmispühad, Πάσχα, Páskar, 復活祭, Pace.
12. 4.	Pro která n,t lze zvolit různé reprezentanty pro systém všech t-prvkových podmnožin n-prvkové množiny? Párování v regulárních bipartitních grafech a souvislost s hranovým barvením. Reprezentanti v projektivních rovinách. Deficitní Hallova věta.
19. 4.	Faktory a faktorizace: Úplný graf na 2^k vrcholech lze 1-faktorizovat, dokonce i každý úplný graf na sudém počtu vrcholů. Sudě regulární graf obsahuje 2-faktor (a tudíž ho jde i 2-faktorizovat).
26. 4.	Toky v sítích: krychle, hyperkrychle a mřížky. Krátká zmínka o grupových tocích.
3. 5.	Vztahy mezi nezávislostí, velikostí největšího párování a nejmenšího vrcholového pokrytí. Hallova a Königova věta přes toky. V k-souvislém grafu existuje mezi každými dvěma množinami vrcholů velikosti k alespoň k vrcholově disjunktních cest. V kubických grafech jsou si hranová a vrcholová souvislost rovny. 2-souvislý graf má silně souvislou orientaci.
10. 5.	Souvislost grafu K_n\C_n. Ušaté lemma pro hranovou 2-souvislost. 2-souvislý rovinný graf je bipartitní právě tehdy, když má všechny stěny ohraničené kružnicemi sudé délky. Počítáme kostry: K_n bez hrany (opakování z přednašky), formule s mazáním a kontrakcemi hran.
17. 5.	Všelijaké ramseyoviny: V dost velké množině přirozených čísel se najdou 3 taková, jejichž součet je dělitelný třemi. Totéž s obarvením množiny. Jak v celočíselné mříži obarvené K barvami najít jednobarevnou podmřížku 2010×2010? Pokud máme dostatečně mnoho bodů v rovině (žádné 3 na přímce), lze z nich vybrat K bodů v konvexní poloze.

Domácí úkoly

datum	ID	body	zadání
22. 2.	cbin	10	Spočtěte C(n,0)-C(n,2)+C(n,4)-... pro n dělitelné čtyřmi (kde C(n,k) je kombinační číslo "n nad k"). Nápověda: zkuste do binomické věty dosazovat komplexní čísla.
	pcom	10	Na cvičení jsme ukázali, že existuje rovinný graf na 5 vrcholech s rovinným doplňkem a pro 11 vrcholů žádný takový neexistuje. Ukažte, jak zlepšit libovolnou z těchto mezí (tím více bodů, čím lépe).
	dens	10	Dokažte, že v rovinném grafu na n vrcholech existuje alespoň n/2 vrcholů, jejichž stupeň je nejvýše 8.
1. 3.	prmd	10	Dokažte, že z odhadu na počet prvočísel mezi n a 2n z cvičení plyne, že π(n) ≤ c*n/log n pro nějakou konstantu n. Nápověda: použijte indukci.
	prml	10	Dokažte, že pokud nějaká mocnina prvočísla p^k dělí C(2n,n), pak je p^k ≤ 2n. Z toho odvoďte, že π(n) ≥ c'*n log n pro nějakou konstantu c'.
	circ	10	Ukažte, že v grafu s minimálním stupněm δ>1 existuje kružnice délky alespoň δ+1.
8. 3.	satr	15	Na cvičení jsme dokázali, že pro šatnářčino číslo š(n) platí rekurence Σ_0≤k≤n C(n,k)*š(n-k) = n!. Odvoďte z ní explicitní vzorec pro š(n) bez použití inkluze a exkluze.
	satd	10	Dokažte, že pro šatnářčino číslo š(n) platí rekurence š(n)=(n-1)(š(n-1)+š(n-2)).
	isol	10	Spočítejte, kolik existuje grafů na množině {1,...,n}, které nemají izolované vrcholy.
	opic	10	Spočítejte, kolik je permutací písmen A až P, v nichž se jako vybraná podposloupnost nevyskytuje žádné ze slov PONK, DOBA, COP, OPICE.
15. 3.	ncom	10	Ukažte, jak počítat zobecněná kombinační čísla C(a,b) pro celočíselné a<0 pomocí klasických kombinačních čísel.
	coef	7	Jak vypadá koeficient u xⁿ v řadě pro (1-3x)^-5?
	genf	7	Nalezněte vytvořující funkci posloupnosti 1,1/2,3,1/4,5,1/6,... (a_n=n+1 pro sudé n, a_n=1/(n+1) pro liché n).
22. 3.	sall	7	Řešte rekurenci a₀=1, a_n+1 = a₀ + a₁ + … + a_n. Nalezněte explicitní vzorec pro n-tý člen.
22. 3.	snon	10	Nehomogenní rekurence: a₀=0, a₁=1, a_n+2=a_n+1 + a_n + 1. Nalezněte explicitní vzorec pro n-tý člen.
29. 3.	grid	15	Spočítejte mřížové cesty z (0,0) do (kn,kn), které se vyhýbají překážkám na souřadnicích (n,n), (2n,2n), &hellip, ((k-1)n,(k-1)n). Stačí rekurentní vzorec.
	tree	10	Najděte bijekci mezi binárními stromy na n vrcholech a pěstovanými stromy na n+1 vrcholech. (Nápověda: Jakou datovou strukturou byste reprezentovali pěstované stromy?)
	tria	10	Triangulací konvexního n-úhelníka nazveme jeho rozdělení na trojúhelníky pomocí nekřížících se úhlopříček. Kolik takových triangulací existuje? Věděl by to pan Catalan?
12. 4.	nolc	10	Z ekvivalence mezi projektivními rovinami a latinskými čtverci víme, že pro prvočíselné N existuje N-1 navzájem ortogonálních latinských čtverců N × N. Sestrojte je explicitně bez použití projektivních rovin.
	ecol	10	Dokažte, že pokud všechny vrcholy daného bipartitního grafu mají stupeň nejvýše k, pak lze hrany grafy obarvit k barvami tak, aby hrany stejné barvy neměly společný vrchol.
	esat	10	Uvažujme logickou formuli v konjunktivní normální formě (formule je konjunkcí klauzulí, každá klauzule je disjunkcí literálů a každý literál je buďto proměnná nebo její negace). Formule je splnitelná, pokud lze za proměnné dosadit 0/1 tak, aby vyšla 1 (true). Splnitelnost bývá obvykle dost těžké rozpoznat. Je to ovšem velice snadné pro formule, v níž každá klauzule obsahuje právě 3 literály a každá proměnná se vyskutuje v právě 3 klauzulích. Taková formule je totiž splnitelná vždy. Dokažte to.
	nnrr	10	Mějme bipartitní graf na N a N vrcholech, jehož každý vrchol má stupeň větší nebo rovný N/2. Dokažte, že v tomto grafu existuje perfektní párování.
	nnbo	5	Kdybychom v předchozím cvičení místo N/2 požadovali N/2-1, již by párování nemuselo existovat. Najděte příklad takového grafu pro libovolně velké N.
19. 4.	tfac	7	Mějme regulární bipartitní graf, jehož vrcholy mají stupně alespoň 2. Dokažte, že v něm existuje 2-faktor.
	khal	10	Pro množinový systém (X,S) definujeme k-systém reprezentantů tak, že vybere z každé množiny k-tici jejích prvků, přičemž všechny vybrané k-tice jsou navzájem disjunktní (1-SRR je tedy SRR podle klasické definice). Ukažte následující analogii Hallovy věty: Množinový systém (X,S) má k-SRR právě tehdy, když se v každém podsystému vyskytuje alespoň k-krát více prvků, než je v něm množin.
	kout	15	Hustotu neprázdného grafu definujeme jako počet hran dělený počtem vrcholů. (Například každý neprázdný rovinný graf má hustotu menší než 3.) Mějme nyní nějaké přirozené číslo h a neorientovaný graf, jehož všechny podgrafy mají hustotu nejvýše h. Ukažte, že graf lze zorientovat tak, aby z každého vrcholu vedlo nejvýše h hran. (Nápověda: Může se hodit věta z předchozího cvičení.)
26. 4.	hykr	10	Spočítejte, kolik má d-rozměrná krychle k-rozměrných stěn.
	mtok	10	Uvažme síť tvaru mřížky {0,…,n-1} × {0,…,n-1}. Hrany jsou orientovány směrem k vyšším souřadnicím, všechny hrany vycházející z vrcholu (x,y) mají kapacitu C(x+y,x) / 2^x+y (kde C(a,b) je kombinační číslo) pro x+y ≤ n-2, ostatní hrany mají kapacitu 1. Určete maximální tok ze zdroje (0,0) do stoku (n-1,n-1).
	ktok	10	Dokažte, že 3-regulární graf má Z₃-tok právě tehdy, je-li bipartitní.
10. 5.	vceq	7	Ukažte, že relace "ležet na společné kružnici" je ekvivalence na hranách a definujte pomocí ní komponenty vrcholové 2-souvislosti.
	eceq	7	Ukažte, že relace "ležet na společném cyklu (neboli uzavřeném tahu)" je ekvivalence na vrcholech a definujte pomocí ní komponenty hranové 2-souvislosti.
	fcol	10	Dokažte, že pokud má 2-souvislý rovinný graf všechny vrcholy sudého stupně, pak je možné jeho stěny obarvit dvěma barvami tak, aby žádné dvě stěny téže barvy nesousedily hranou.
	pcon	10	Najděte největší K, pro které ještě existuje vrcholově K-souvislý rovinný graf.
	kokr	10	Spočítejte, kolik koster má graf 3-rozměrné krychle.
	kohy	10	Spočítejte, kolik koster má graf 7-rozměrné krychle (můžete si na to napsat program).
	koko	10	Spočítejte, kolik koster má loukoťové kolo o N vrcholech (kružnice délky N-1 + jeden vrchol spojený se všemi osatními). Stačí rekurentní vzorec, +5 bodů za explicitní (bez sum, rekurze a podobných operací).
17. 5.	aseq	10	Dokažte, že pro nějaké dost velké N platí, že obarvíme-li čísla 1, …, N nějakým pevným počtem barev, existují mezi nimi 3 čísla x,y,z stejné barvy, pro něž platí x+y=z.