Cvičení z Kombinatoriky a grafů I

Ve školním roce 2001/2002 vedu cvičení z předmětu Kombinatorika a grafy I (DMI011). Cvičení se koná každé pondělí od 15.40 v posluchárně E1.

Podmínkou k získání zápočtu je vyřešení alespoň pěti příkladů, buďto na cvičení nebo písemně (lze odevzdat do té doby, než někdo řešení na cvičení předvede). Pokud nestihnete příklady odevzdat během semestru, zvyšuje se požadovaný počet na 8.

Příklady

Datum	Příklady
1. 10.	Dokažte, že množina je konečná právě tehdy, když každá dvě její lineární uspořádání jsou navzájem isomorfní.
	Vyslovte a dokažte charakteristiku skóre stromu (tedy které posloupnosti přirozených čísel jsem skóre nějakého stromu a které nikoliv).
	Nalezněte nekonečně mnoho 3-souvislých 3-regulárních rovinných grafů. [vyřešeno]
	Dokažte, že stěny každého sudého rovinného grafu lze obarvit dvěma barvami.
8. 10.	Dokažte, že projektivní rovina řádu N existuje právě tehdy, když existuje N-1 navzájem ortogonálních latinských čtverců velikosti NxN.
8. 10.	Dokažte indukcí podle x Malou Fermatovu větu (ta říká, že x^p mod p = x, pokud je p prvočíslo a x číslo nesoudělné s p).
15. 10.	Cvičení se nekonalo.
22. 10.	Rozhodněte, zda věta o počítání koster pomocí determinantů platí i pro multigrafy.
22. 10.	Odvoďte vztah pro počet koster grafu K_m,n (úplného bipartitního grafu).
29. 10.	Spočtete kružnice v grafech K_n a K_m,n.
	Ukažte, jak závisí počet eulerovských množin (tj. podgrafů se všemi stupni sudými) na počtu vrcholů, hran a komponent grafu.
	Ukažte, že v rovinném grafu tvoří bázi prostoru všech kružnic kružnice určené všemi stěnami mimo vnější stěny.
5. 11.	Najděte bázi prostoru kružnic v pravoúhlé mřížce m krát n.
	Snadno se dokáže, že Ford-Fulkersonův algoritmus se pro každou síť s racionálními vahami zastaví. Nalezněte síť s vahami iracionálními, na které může cyklit do nekonečna.
	V jednom švýcarském sklepě byla-nebyla krychle výborného sýra o hraně 7 jednotek; objevili jste ji ovšem nejen vy, ale také jedna šikovná švýcarská myš. Ledva ji zmerčila, začala se krychlí prokousávat od rohu se souřadnicemi (0,0,0), a to tak, že vždy lezla rovnoběžně s hranami krychle po bodech s celočíselnými souřadnicemi. Rozhodla se, že všechen sýr sní, že žádným jednou prožraným bodem už vícekrát nepůjde a že skončí svoji pouť ve středu spodní hrany čelní stěny (tj. v bodě (3,6,0)). Dokažte jí, že to není možné a že má raději vylézt v bodě (6,6,6), kde to možné je.
12. 11.	Zůstávají úkoly z minula.
19. 11.	Dokažte, že v každém vrcholově 2-souvislém grafu leží každé dva vrcholy na společné kružnici.
19. 11.	Dokažte, že pro každý graf na alespoň k+1 vrcholech platí, že je k-souvislý právě tehdy, když pro libovolné dvě disjunktní množiny vrcholů A, B velikosti k platí, že mezi nimi existuje k vrcholově disjunktních cest.
26. 11.	Dokažte, že relace "být hranově 2-souvisle propojený" (tj. ležet na společném cyklu) je ekvivalencí na vrcholech, zatímco "být vrcholově 2-souvisle propojený" (tj. ležet na společné kružnici) je ekvivalencí na hranách. Jak byste pomocí těchto relací definovali komponenty vrcholové a hranové 2-souvislosti?
	Ukažte, že pro graf G na alespoň k+1 vrcholech platí, že G je vrcholově k-souvislý právě když každé 2 množiny vrcholů X, Y velikosti k jsou propojeny k vrcholově disjunktními cestami.
	Vyslovte a dokažte obdobné tvrzení pro hranovou k-souvislost.
3. 12.	Dokažte, že každý rovinný graf má nakreslení, jehož všechny hrany jsou úsečky a každá stěna mimo vnější je konvexní mnohoúhelník. (Hint: upravte důkaz Kuratowského věty.)
3. 12.	Ukažte, že si při hledání rovinného nakreslení podle Kuratowského věty můžete zvolit hranu, která bude na vnější stěně.
10. 12.	Rozhodněte, zda platí: (a) každý 3-regulární souvislý graf má perfektní párování, (b) 3-regulární a hranově 2-souvislý, (c) 3-regulární a vrcholově 2-souvislý.
17. 12.	Dokažte, že binárních stromů na n vrcholech (pokud má vrchol jediného syna, stejně rozlišujte, zda je to syn levý nebo pravý) je stejně jako rovinných stromů na n+1 vrcholech (tj. stromů s vrcholy libovolného stupně, v nichž si vybereme kořen a každý vrchol má definováno pořadí synů). (Hint: Na všechny dnešní příklady se hodí vytvořující funkce)
	Ukažte, že korektní uzávorkování s n levými a n pravými závorkami jsou až na posunutí počítána Catalanovými čísly.
	Spočtěte různá vydláždění obdélníka 2 krát n jednotkových čtverečků dominovými kostkami (1 krát 2 čtverečky).
	Spočtěte, kolik je v mřížce velikosti n krát n mřížových cest vedoucích z levého dolního rohu do pravého horního stále směrem nahorů nebo doprava, a to tak, že nikdy nepřekročí hlavní diagonálu mřížky (dotknout se jí mohou).
	Spočtěte, kolik je posloupností délky n složených z nul a jedniček takových, že se v nich nikde nevyskytnou dvě nuly za sebou.
	Odvoďte obecný vzorec pro 1³ + 2³ + 3³ + 4³ + ... + n³.
	(*) Jak zkonstruovat z vytvořující funkce posloupnosti a₀, a₁, a₂, ... vytvořující funkci pro a₀, a₂, a₄, ... ?
7. 1.	Zůstávají úkoly z minula.