Cvičení z Kombinatoriky a grafů I

Ve školním roce 2003/2004 vedu cvičení z předmětu Kombinatorika a grafy I [NDMI011]. Cvičení se koná každé úterý od 15:40 v posluchárně E3.

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
30. 9.	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.
	ktah	2	Charakterizujte neorientované grafy, které je možno nakreslit k tahy (ať již uzavřenými nebo otevřenými, na tom nesejde).
	inft	1	Dokažte, že v každém nekonečném binárním stromu existuje nekonečně dlouhá cesta.
	hypl	2	Spočtěte, na kolik částí rozdělí n-rozměrný prostor k nadrovin.
7. 10.	komu	3	Rozhodněte, zda věta o počítání koster pomocí determinantů platí i pro multigrafy (upravíme-li vhodně definici Laplaceovy matice).
	kobi	2	Spočtěte, kolik koster má úplný bipartitní graf K_m,n.
	rank	1	Dokažte, že hodnost Laplaceovy matice grafu je n-k, kde k je počet komponent grafu.
14. 10.	koko	2	Spočtěte, kolik koster má kolo W_n (to je kružnice na n vrcholech doplněná o střed, ke kterému jsou připojené všechny ostatní vrcholy). Pravděpodobně vám vyjde rekurentní formule, pokud ji dokážete převést na uzavřenou formuli (tj. bez rekurze), budete o bod bohatší.
	kokr	1	Spočtěte, kolik koster má graf krychle.
	numc	2	Nalezněte formule pro počet kružnic v K_n a K_m,n.
	kohy	4	Spočtěte, kolik koster má n-rozměrná hyperkrychle Q_n. (To 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.) [Zatím neumím vyřešit.]
21. 10.	plba	2	Dokažte, že pro libovolné rovinné nakreslení rovinného grafu bez mostů platí, že množina všech hraničních kružnic stěn s výjimkou vnější stěny tvoří bázi prostoru cyklů.
	nzkr	1	Cirkulaci s hodnotami z grupy Z_k, která nemá na žádné hraně nulovou hodnotu, budeme nazývat k-NZF (non-zero flow). Nalezněte 4-NZF v grafu krychle Q₃.
	nz4c	3	Dokažte, že tvrzení "Každý rovinný graf bez mostů má 4-NZF" je ekvivalentní se známou větou o 4 barvách ("Stěny každého rovinného grafu je možno obarvit tak, aby žádné 2 stěny sousedící hranou neměly stejnou barvu.").
28. 10.			Cvičení se nekonalo (státní svátek).
4. 11.	fppa	2	Dokažte, že axiom netriviálnosti konečné projektivní roviny je ekvivalentní s tvrzením "existují alespoň 3 body a všechny body není možno pokrýt dvěma přímkami".
4. 11.	fpp3	2	Sestrojte konečnou projektivní rovinu řádu 3.
11. 11.	krfl	2	Nalezněte v hyperkrychli Q_n (definice viz výše), která má na všech hranách jednotkové kapacity a) maximální celočíselný tok b) maximální tok takový, že po každé hraně teče nenulové množství.
18. 11.	2ecc	1	Rozhodněte, zda hranově 2-souvislé grafy jsou právě ty, ve kterých každé dva vrcholy leží na společném cyklu (tj. uzavřeném tahu).
	cokr	2	Spočtěte, jaký je stupeň hranové souvislosti n-rozměrné hyperkrychle Q_n.
	copl	3	Ukažte, kolika-souvislý může být rovinný graf (vrcholově).
25. 11.	equi	2	Dokažte, že "ležet na společném cyklu" je ekvivalence na vrcholech, zatímco "ležet na společné kružnici" je ekvivalence na hranách a nadefinujte pomocí toho komponenty vrcholové a hranové 2-souvislosti.
25. 11.	spat	2	Ukažte, že mosty v grafu jsou právě hrany ležící v průniku všech koster.
2. 12.	plin	3	Dokažte, že každý rovinný graf má rovinné nakreslení, v němž jsou všechny hrany úsečky. (Hint: Upravte konstrukci nakreslení z důkazu Kuratowského věty, viz dnešní cvičení.)
2. 12.	mino	2	Graf H se nazývá minorem grafu G právě tehdy, když lze H získat z G posloupností operací smazání vrcholu, smazání hrany a kontrakce hrany (násobné hrany splynou). Dokažte, že rovinné grafy jsou právě ty, jejichž minorem není K_3,3 ani K₅.
9. 12.	defh	2	Dokažte "deficitní" verzi Hallovy věty: Pokud pro každý podsystém P množinového systému M platí, že sjednocení všech množin z P obsahuje alespoň velikost(P)-k prvků, pak existuje systém různých reprezentantů všech množin z M až na nějakých k.
	2fac	3	Dokažte, že každý 2k-regulární graf obsahuje 2-faktor. (j-faktor grafu G je takový jeho podgraf, který je j-regulární a pokrývá všechny vrcholy G.) [Hint: šikovně roztrhněte vrcholy na poloviny.]
	1fab	2	Rozhodněte zda platí, že má-li k-regulární graf perfektní párování, pak toto párování obsahuje všechny mosty grafu.
	infh	3	"Nekonečná verze" Hallovy věty by se dala formulovat takto: Nekonečný systém množin má systém různých reprezentatnú právě tehdy (kdyžž) každý konečný podsystém splňuje Hallovu podmínku. Toto tvrzení ovšem neplatí. 1 bod za protipříklad 2 body za dúkaz toho, že omezíme-li se na systémy nekonečně mnoha konečně vëlkých množin, tak už platit bude.
16. 12.	grid	2	Mějme nekonečně velké americké město (čili nekonečnou mřížku Z², přičemž každý bod mřížky odpovídá jednomu domu). Santa Claus jako každý rok rozváží dárečky do všech domů (do každého jeden), ale jelikož i jeho elfové mají omezenou fantazii, dárečků existuje pouze 2004 různých druhů. Dokažte, že ať dárečky rozveze jakkoliv, vždy bude existovat 2004 řádků a 2004 sloupců takových, že ve všech domech ležících na průsečíku těchto řádků s těmito sloupci dostanou stejný typ dárečku.
6. 1.	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ř. Tento a následující příklady lze odevzdávat za plný počet bodů do konce zkouškového období.
	trbi	1	Na cvičeních jsme spočítali, ž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.
	domi	1	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).
	grpa	2	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).
	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.
	zone	1	Spočtěte n-prvkové posloupnosti nul a jedniček takové, že se v nich nikdy nevyskytnou 2 nuly za sebou.