Cvičení z Kombinatoriky a grafů I

Ve školním roce 2004/2005 vedu cvičení z předmětu Kombinatorika a grafy I (DMI011). Cvičení se koná každé úterý od 10:40 v posluchárně E1.

Podmínkou k získání zápočtu je vyřešení příkladů za alespoň 8 bodů, buďto písemně nebo e-mailem. Body uvedené v tabulce příkladů platí během semestru, pak se redukují na polovinu.

Příklady

Datum	ID	Body	Příklady
5. 10.	hypl	1	Mějme n rovin v obecné poloze v 3-rozměrném prostoru. Na kolik částí tyto roviny prostor rozdělí? (*) +1 bod: totéž pro n nadrovin v k-rozměrném prostoru.
	trsc	1	Charakterizujte posloupnosti, které jsou skórem stromu.
	dens	1	Dokažte, že v rovinném grafu na n vrcholech existuje alespoň n/2 vrcholů, jejichž stupeň je nejvýše 8.
	5col	3	Sestrojte algoritmus, který v lineárním čase nalezne obarvení zadaného rovinného grafu pěti barvami.
	vspe	2	Mějme množinu všech hranových podgrafů nějakého grafu (tedy takových, které mají tutéž množinu vrcholů jako onen graf, ale pouze vybrané hrany), které obsahují sudý počet hran. Dokažte, že tato množina spolu s operací symetrického rozdílu (xor) tvoří vektorový prostor nad tělesem Z₂. Spočtěte jeho dimenzi a nalezněte bázi.
12. 10.			Zaskakoval Robert Šámal, žádné domácí úkoly nebyly.
19. 10.	numc	2	Nalezněte formule pro počet kružnic v K_n a K_m,n.
	2col	2	Dokažte, že stěny každého rovinného grafu se všemi stupni vrcholů sudými lze obarvit dvěma barvami tak, aby žádné dvě stěny sousedící hranou neměly stejnou barvu.
	bipm	2	Pro každé n nalezněte nejmenší k takové, že pro každý bipartitní graf G na n vrcholech s maticí sousednosti A platí, že G je souvislý právě tehdy, když A^k + A^k-1 neobsahuje žádné nuly.
26. 10.	komu	2	Rozhodněte, zda věta o počítání koster pomocí determinantu platí i pro multigrafy.
	chro	3	Dokažte, že pro každý graf G existuje polynom p takový, že p(k) udává počet obarvení grafu G pomocí k barev. Hint: použijte podobnou rekursivní formuli jako pro počet koster, ale na komplement daného grafu.
	spbr	1	Dokažte, že mosty v grafu jsou právě hrany ležící v průniku všech jeho koster.
	kobi	2	Spočtěte kostry úplného bipartitního grafu K_m,n.
	kokr	1	Spočtěte kostry 3-rozměrné krychle. (*) +3 body: totéž pro k-rozměrnou krychli.
	koko	2	Kolo s loukotěmi W_n je graf skládající se z kružnice C_n a vrcholu, který je spojen se všemi vrcholy na kružnici. Spočtěte kostry grafu W_n. 2 body za rekurentní formuli, bod navíc za explicitní vzorec (hint: vytvořující funkce).
	regu	3	Dokažte, že je-li k dostatečně velké, pak pro každý souvislý k-regulární graf platí, že má více eulerovských podgrafů než koster. Hint: Využijte toho, že determinant matice je součinem vlastních čísel, čili ho lze shora odhadnout mocninou největšího vlastního čísla; zkombinujte s odhadem vlastních čísel Laplaceovy matice.
2. 11.	cpla	2	Zjistěte maximální možný stupeň vrcholové souvislosti rovinného grafu.
2. 11.	balo	2	Dokažte, že každý graf je možno zorientovat tak, aby se vstupní a výstupní stupeň každého vrcholu lišily maximálně o 1.
9. 11.	2edg	2	Dokažte, že vrcholově 2-souvislé jsou právě ty grafy, ve kterých každé dvě hrany leží na společné kružnici. Hint: dokažte nejdříve, že každý vrchol a hrana leží na společné kružnici.
	3reg	1	Dokažte, že pro 3-regulární grafy je vrcholová a hranová 2-souvislost totéž.
	wfof	1	Naivní Ford-Fulkersonův algoritmus, který bude zlepšovat pouze podél cest orientovaných ve směru ze zdroje do spotřebiče, nefunguje. Nalezněte protipříklad.
16. 11.	hkfl	2	Hyperkrychle dimenze n (značí se obvykle Q_n) je graf, jehož vrcholy jsou všechny n-složkové vektory nad Z₂ a z v do w vede hrana právě tehdy, když w vznikne z v změnou právě jedné nulové složky na jedničkovou. Z Q_n vyrobíme síť, ve které bude vrchol 00...0 zdroj, 11...1 spotřebič a na všech hranách budou jednotkové kapacity. Nalezněte: a) maximální celočíselný tok, b) maximální nenulový tok (tj. takový, že po každé hraně něco teče).
	hkco	1	Spočtěte stupeň hranové souvislosti grafu Q_n (zobecněte výsledek předchozího příkladu).
	kncn	2	Určete stupeň vrcholové souvislosti úplného grafu na n vrcholech po vynechání hamiltonovské kružnice.
23. 11.	e3e3	2	CNF-formule je logická formule ve formě konjunkce (logického součinu) klauzulí, přičemž každá klauzule je disjunkcí (logickým součtem) literálů, což jsou buďto proměnné nebo jejich negace. E3E3-formule je CNF-formule, ve které každá klauzule obsahuje právě 3 proměnné a každá proměnná se vyskytuje v právě třech klauzulích. Dokažte, že každá E3E3-formule je splnitelná (tj. že je možno dosadit za proměnné pravdivostní hodnoty tak, aby celá formule byla pravdivá). Hint: Párování.
	kn1f	2	Rozhodněte, zda je úplný graf na sudém počtu vrcholů možno 1-faktorizovat (rozdělit jeho hrany do hranově disjuktních perfektních párování).
	2fac	3	Dokažte, že v každém 2j-regulárním grafu existuje 2-faktor. [k-faktor je k-regulární podgraf obsahující všechny vrcholy] Hint: Rozdělte šikovně vrcholy na poloviny.
	kong	2	Dokažte Königovu větu: Velikost minimálního vrcholového pokrytí bipartitního grafu [v.p. je množina vrcholů, která inciduje s každou hranou] je rovna velikosti maximálního párování v tomto grafu.
30. 11.	fpp3	1	Sestrojte konečnou projektivní rovinu řádu 3. (*) +1 bod: řádu 4.
	nolc	1	Jiná konstrukce projektivních rovin: Mějme konečné těleso T a sestrojme matice M_i pro všechna nenulová i ∈ T, a to tak, že M_i(x,y)=ix+y (x,y ∈ T). Dokažte, že M_i tvoří navzájem ortogonální latinské čtverce.
	flt	1	Dokažte Malou Fermatovu větu: pro každé prvočíslo p a číslo x nesoudělné s p platí, že x^p-1 mod p=1. Hint: Indukce podle x.
7. 12.	unpl	3	Dokažte, že každá 2 rovinná nakreslení vrcholově 3-souvislého grafu jsou kombinatoricky ekvivalentní (tj. stěny obsahují tytéž vrcholy).
7. 12.	orpl	2	Rozhodněte, zda je možné každý rovinný graf zorientovat tak, aby z každého vrcholu vycházely nejvýše 3 hrany.
14. 12.	tric	2	Dokažte, že triangulace každého rovinného grafu na alespoň čtyřech vrcholech je vrcholově 3-souvislá. (Triangulace je doplnění hran takové, aby se ze všech stěn staly trojúhelníky.)
14. 12.	spdr	2	Rozhodněte, zda lze každý graf nakreslit do 3-rozměrného euklidovského prostoru tak, aby vrcholy odpovídaly bodům a hrany byly nekřížící se úsečky.
21. 12.	cbth	2	Sečtěte (n 0)-(n 2)+(n 4)-(n 6)+...-...+(n n), kde (a b) je kombinačňí číslo "a nad b" a n je násobek čtyř. Hint: Binomická věta.
	trbi	2	Dokažte, že rovinných stromů (určen kořen a pořadí synů každého vrcholu) na n vrcholech je stejně jako binárních stromů (určen kořen a levý a pravý syn každého vrcholu [libovolný ze synů může chybět]) na n-1 vrcholech. Sestrojte příslušnou bijekci.
	sqre	2	Odvoďte explicitní vzorec pro 1²+2²+...+n².
	brac	2	Spočtěte různá korektní uzávorkování s n levými a n pravými závorkami.
4. 1.	dom2	1	Spočtěte, kolik je různých vydláždění obdélníka 2 krát n dominovými kostkami. Tento a následující příklady lze odevzdávat za plný počet bodů do konce zkouškového období.
4. 1.	dom3	3	Spočtěte, kolik je různých vydláždění obdélníka 3 krát n dominovými kostkami.
11. 1.			Rozdávaly se zápočty, nikoliv úkoly.