Cvičení z Kombinatoriky a grafů I

Ve školním roce 2002/2003 vedu cvičení z předmětu Kombinatorika a grafy I [NDMI011]. Cvičení se koná každý pátek od 9.00 v posluchárně E4.

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
18. 10.	Dokažte, že spočetná množina je konečná právě tehdy, když všechna její lineární uspořádání jsou navzájem isomorfní.
	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.
	Charakterizujte neorientované grafy, které je možno nakreslit k tahy (ať již uzavřenými nebo otevřenými, na tom nesejde).
25. 10.	Pomocí prostorů řezů a cyklů dokažte, že bipartitní grafy jsou právě grafy bez lichých kružnic.
25. 10.	Dokažte, že vrcholy každého grafu lze rozdělit do dvou množin tak, aby z každého vrcholu vedl sudý počet hran do vrcholů ležících v téže množině.
1. 11.	Všude nenulová k-cirkulace (též řečená k-NZF) je přiřazení nenulových čísel z k-prvkového tělesa hranám grafu, které splňuje Kirchhoffův. Dokažte, že graf 3-rozměrné krychle má 4-NZF.
1. 11.	(*) Dokažte, že tvrzení "každý rovinný graf bez mostů má 4-NZF" je ekvivalentní se známou větou o 4 barvách ("každý rovinný graf lze obarvit čtyřmi barvami tak, aby každá hrana byla dvoubarevná").
8. 11.	(*) Snadno se dokáže, že Ford-Fulkersonův algoritmus se pro každou síť s racionálními vahami zastaví. Nalezněte síť s některými vahami iracionálními, na které může cyklit do nekonečna.
8. 11.	n-rozměrná krychle H_n je definována takto: vrcholy jsou všechny uspořádané n-tice nul a jedniček, hrana vede z vrcholu x do vrcholy y právě tehdy, když y vznikne z x změnou právě jedné jedničky na nulu. Když přiřadíme všem hranám jednotkové kapacity, vrchol "samé nuly" prohlásíme za zdroj a vrchol "samé jedničky" za stok, vznikne síť. Nalezněte v této síti maximální tok: a) takový, že po každé hraně poteče buďto 0 nebo 1 b) jiný, který bude na každé hraně nenulový.
15. 11.	Dokažte (nebo vyvraťte), že hranově 2-souvislé jsou právě ty grafy, v nichž leží každé dvě hrany na společném cyklu.
	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. To využijte k definici komponent vrcholové a hranové 2-souvislosti.
	Určete stupeň hranové souvislosti grafu H_n.
22. 11.	Dokažte pomocí Ramseyovy věty Shurovu větu: pro každé k platí, že pro dostatečně velké n se v libovolném obarvení prvních n přirozených čísel k barvami vždy naleznou x, y, z stejné barvy, pro která je x+y=z.
29. 11.	Cvičení se nekonalo.
6. 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ý.
6. 12.	Vymyslete algoritmus na nalezení maximálního párování (tj. s největším možným počtem hran) v bipartitním grafu. Hint: Zkuste úlohu převést na hledání toku v šikovně zvolené síti.
13. 12.	Dokažte deficitní verzi Hallovy věty pro systémy různých reprezentantů: pokud pro každý podsystém množin platí, že jeho sjednocení je maximálně o k menší než je počet množin v podsystému, pak po odstranění nějakých k množin existuje systém různých reprezentantů. Hint: přidejte si vhodné množiny.
	(*) Dokažte, že každý 2k-regulární graf obsahuje 2-faktor. Hint: rozdělte šikovně vrcholy.
	Nekonečná varianta Hallovy věty: "spočetný systém nejvýše spočetných množin má systém různých reprezentantů právě tehdy když Hallova podmínka platí pro každý konečný podsystém." To ovšem není pravda, najděte protipříklad.
	Dokažte, že pokud budou všechny množiny konečné, tak už Nekonečná Hallova věta funguje.
20. 12.	Rozhodněte, zda platí následující tvrzení: Je-li G regulární graf, pak každý jeho 1-faktor obsahuje všechny mosty.
	Ukažte, že každý úplný graf na sudém počtu vrcholů je možno 1-faktorizovat, tj. rozložit jeho hrany na disjunktní sjednocení 1-faktorů.
	Buď X n²+n+1-prvková množina a S systém n²+n+1 podmnožin X, přičemž každá podmnožina má n+1 prvků a každé dvě podmnožiny z S mají nejvýše jeden společný prvek. Dokažte, že za těchto podmínek vždy existuje systém různých reprezentantů množin z S.
	Spočtěte, kolik koster má úplný bipartitní graf K_m,n.
3. 1.	Cvičení bylo velmi komorní, až málem nebylo komu domácí úkoly zadávat :)
10. 1.	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)
	... ale také je možné explicitně sestrojit bijekci, zkuste to.
	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₄, ... ?
	Sečtěte (n 0)-(n 2)+(n 4)-(n 6)+...-..., kde (a b) je kombinačňí číslo "a nad b" a n je násobek čtyř.