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

DatumIDBodyPříklady
30. 9. 2col2Dokaž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.
ktah2Charakterizujte neorientované grafy, které je možno nakreslit k tahy (ať již uzavřenými nebo otevřenými, na tom nesejde).
inft1Dokažte, že v každém nekonečném binárním stromu existuje nekonečně dlouhá cesta.
hypl2Spočtěte, na kolik částí rozdělí n-rozměrný prostor k nadrovin.
7. 10. komu3Rozhodněte, zda věta o počítání koster pomocí determinantů platí i pro multigrafy (upravíme-li vhodně definici Laplaceovy matice).
kobi2Spočtěte, kolik koster má úplný bipartitní graf Km,n.
rank1Dokažte, že hodnost Laplaceovy matice grafu je n-k, kde k je počet komponent grafu.
14. 10. koko2Spočtěte, kolik koster má kolo Wn (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ší.
kokr1Spočtěte, kolik koster má graf krychle.
numc2Nalezněte formule pro počet kružnic v Kn a Km,n.
kohy4Spočtěte, kolik koster má n-rozměrná hyperkrychle Qn. (To je graf, jehož vrcholy jsou všechny n-složkové vektory nad Z2 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. plba2Dokaž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ů.
nzkr1Cirkulaci s hodnotami z grupy Zk, která nemá na žádné hraně nulovou hodnotu, budeme nazývat k-NZF (non-zero flow). Nalezněte 4-NZF v grafu krychle Q3.
nz4c3Dokaž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. fppa2Dokaž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".
fpp32Sestrojte konečnou projektivní rovinu řádu 3.
11. 11. krfl2Nalezněte v hyperkrychli Qn (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. 2ecc1Rozhodně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).
cokr2Spočtěte, jaký je stupeň hranové souvislosti n-rozměrné hyperkrychle Qn.
copl3Ukažte, kolika-souvislý může být rovinný graf (vrcholově).
25. 11. equi2Dokaž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.
spat2Ukažte, že mosty v grafu jsou právě hrany ležící v průniku všech koster.
2. 12. plin3Dokaž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í.)
mino2Graf 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í K3,3 ani K5.
9. 12. defh2Dokaž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.
2fac3Dokaž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.]
1fab2Rozhodněte zda platí, že má-li k-regulární graf perfektní párování, pak toto párování obsahuje všechny mosty grafu.
infh3"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. grid2Mějme nekonečně velké americké město (čili nekonečnou mřížku Z2, 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. cbth2Seč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í.
trbi1Na 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.
domi1Spoč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).
grpa2Spoč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).
sqre2Odvoďte explicitní vzorec pro 12+22+...+n2.
brac2Spočtěte různá korektní uzávorkování s n levými a n pravými závorkami.
zone1Spočtěte n-prvkové posloupnosti nul a jedniček takové, že se v nich nikdy nevyskytnou 2 nuly za sebou.
Stránku spravuje Martin Mareš