Cvičení z Kombinatoriky a grafů I, středa 12:20 S7 a středa 15:40 S10

Na této stránce se dozvíte informace, ke cvičení, které v letním semestru 2008/2009 vedu.

Pokud jste zabloudili, vraťte se zpět na mojí hlavní stránku.

Mohl by se vám hodit odkaz na stránky přednášejícího. Zdůrazňuji, že obě cvičení jsou určena k "prvácké" přednášce Dr. Pangráce, případně Prof. Loebla, nikoliv k "druhácké" přednášce Prof. Kratochvíla a Doc. Valtra. Vzhledem k tomu, že přednášky jsou značně rozdílné, silně doporučuji druhákům (a starším), aby si našli cvičení k jejich přednášce. Druhácká cvika jsou prý přeplněná, takže je pro vás asi lepší chodit na prvácká, než nikam, i když se neprocvičí všechno to, co budete potřebovat k druhácké zkoušce a především k bakalářským státnicím. Které cvičení patří ke které přednášce lze poznat například v seznamu pod rozvrhem ve sloupci studenti.

Jak mne sehnat

Vyskytuji se v místnosti 125 na Malé Straně, ale nikoli příliš často ani pravidelně. Takže pokud se mne rozhodnete navštívit osobně, ať už kvůli odevzdání příkladů, konzultaci, nebo zapsání zápočtu, je více než vhodné se předem domluvit mejlem (suchy@kam).

Ve středu 13.5. se cvičení nekonala, neboť byl rektorský sportovní den.

Většinu září budu pravděpodobně mimo Prahu, pravděpodobně nebudu mít příliš přístup k internetu, takže pravděpodobně nebudu opravovat příklady a a v některých termínech určitě nebudu fyzicky k zastižení. Doporučuji všem studentům, kteří chtějí získat zápočet, aby tak učinili do konce srpna.

Podmínky pro získání zápočtu

Vzhledem k tomu, že je o moje cvičení zvýšený zájem a příslušné místnosti nejsou nafukovací (neměli byste kde sedět na písemku), je nutné se na cvičení zapsat pomocí Grupíčku.

Každý týden budou zadány domácí úkoly za cca 10 bodů (poslední "bonusová" série za 25 bodů), 6. 5. 2009 se psala těžká písemka za 40 bodů. Na odevzdávání domácích úkolů není žádný časový limit.

Podmínkou pro zisk zápočtu je zisk alespoň 50 bodů (v součtu). Zápočty zapisuji já - elektronicky, jakmile na něj získáte nárok (viz Průbežné výsledky), propiskou až ke mně poté přijdete. Na vaší účasti na cvičeních netrvám.

Vypracované příklady můžete nejlépe přinést osobně (viz Jak mne sehnat) na nějakém vhodném médiu (Papír, USB klíčenka, folie pro projektor, CD, DVD, disketa, hliněná destička, ...), případně posílat mejlem, v nějakém vhodném formátu (.ps, .pdf, (La)TeX, prosty text, naskenovaný rukopis, OpenOffice document format, MS Word :-), MS Powerpoint, ...). Obojí v dostatečném předstihu (nejlépe několik dní) před zkouškami, může se stát, že tu nebudu, nebo že vašich několik desítek příkladů neopravím během hodiny. Také nedoporučuji posílat přiklady tak, aby to přesně vyšlo do 50i bodů. Nikdo nejsme neomylní a (dle zákona schválnosti) nejspíš zrovna v těchle příkladech tu chybu uděláte. Nějaká rezerva vám určitě neuškodí.

Vždy se snažte, ať je z řešení poznat (raději to tam napište), co děláte, jak to děláte (které věty jste použili apod.), proč to děláte a kolik to vyšlo. Výsledky je třeba zdůvodnit, i když to není explicitně napsáno. Samotný výsledek má mizivou bodovou hodnotu.

Probraná témata

Příklady na doma

Číslo příkladu Zadání Body
1.1 Student udělá určitou chybu v příkladu 1.1 s pravděpodobností p. Tato pravděpodobnost je samozřejmně zcela nezávislá na tom zda tuto chybu udělají ostatní studenti, neboť studenti řeší domácí úkoly samostatně!!!
a)Adam a Bedřich tento příklad řeší, jaká je pravděpodobnost, že nikdo z nich chybu neudělá?
b)Jaká je střední hodnota počtu udělaných chyb řeší-li příklad všech n studentů z kruhu?
c)Víme-li, že jeden konkrétní student z kruhu tuto chybu udělal (nechci jmenovat), jaká je pravděpodobnost, že ji udělá ještě někdo další?
Řešte vždy nejdříve obecně a pak pro p = 0,1 a n = 20.
3
1.2Ve hře štastných deset jsou postupně z osudí náhodně taženy míčky s čísly 1,2,...,80. Vytažené míčky se už do osudí nevracejí.
a)Jaká je pravděpodobnost, že součin prvních dvou tažených čísel bude 16?
Označme jev z bodu a) jako jev A. Označme jako jev B, že jako první byl tažen míček s číslem 1. B' je doplněk B. Určete podmíněnou pravděpodobnost jevu A,
b)nastal-li jev B, tj. P(A|B).
c)nenastal-li jev B ,tj. P(A|B').
3
1.3Podobně jako v předchozím příkladě losojume míčky, tentokrát jen s čísly 1 až 6. Určete střední hodnotu součinu čísel na prvních dvou vytažených míčcích.
Hint: možnosti, které nenastávají, do součtu přičtěte a zase odečtěte.
2
2.série
3.série
4.1Kombinatoricky dokažte, že pro každé 0 <= k <= (n-1)/2 platí, že počet (k+1)-prvkových podmnožin n-prvkové množiny je aspoň počet k-prvkových podmnožin n-prvkové množiny (t.j. dokažte to bez využití toho, že příslušný počet podmnožin je n! /(k!(n-k)!).2
4.2Nechť X = {-23, -22, ..., 186} a nechť množina Y vznikne z množiny X tak, že z ní vyškrtáme všechny násobky čísel 6,9,15,18,24,30. Zjistěte, kolik prvků obsahuje množina Y.2
4.3O přirozeném čísle n řekneme, že je bezčtvercové pokud n není dělitelné číslem k2, pro žádné k ≥ 2 přirozené. Zjistěte kolik bezčtvercových čísel se nachází v intervalu 134, 135, ..., 522.3
5.1Pomocí vhodné kombinatorické interpretace a použitím principu inkluze a exkluze spočítejte následující sumu pro n,m,j přirozené a n ≤ j ≤ m + n (t.j. vyjádřete tuto sumu jako nějaký výraz, který už dále nebude obsahovat sumu)
4
5.2Spočítejte počet surjektivních ("na") zobrazení z množiny X do množiny Y, kde |X| = n a |Y| = m (a příslušný výraz se pokuste upravit do co nejjednoduššího tvaru).3
5.3Kolika způsoby můžeme rozsadit n manželských párů okolo kruhového stolu s 2n židlemi tak, aby žádný manželský pár neseděl vedle sebe.3
6.1Najděte vytvořující funkce posloupností {12, 22, 32, 42, ...}, {1,-1, 2,-2, 3,-3, 4,-4, ...} a { 1/1 , 1/2, 1/3, 1/4, ...}.2+2+2
6.2Pomocí vytvořujících funkcí najděte explicitní vzorec pro sumu 12+ 22 + 32 + .. + n2.3
6.3Najděte koeficient u x^3 ve výrazu: ((3-4x)3/2)/(1-x).2
7.1Uvažme posloupnost, v níž druhý a každý další člen je průměrem předchozích dvou, tj. pro n ≥ 2 platí an = (an-1 + an-2)/2. Určete limitu této posloupnosti v závislosti na členech a0 a a1.3
7.2Pro posloupnost platí a0 = 1 a pro všechna n ≥ 0 je an+1=2an+3. Pomocí vytvořujících funkcí určete vzorec pro n-tý člen této posloupnosti.3
7.3Kolika způsoby lze nakoupit 100 balení pseudoefedrinu ve čtyřech lékárnách, mají-li v nich na skladě 64, 48, 29 a 17 balení. Vyjde-li Vám součet (nejvýše patnácti) součinů kombinačních čísel, nemusíte (ale můžete) výsledné číslo dopočítávat.2
7.4Pro všechna n ≥ 0 spočítejte počet pn posloupností nul a jedniček délky n neobsahujících dvě nuly těsně za sebou. Cílem je vzorec v uzavřeném tvaru.2
8.1Určete počet zn platných závorkování s n levými závorkami. Závorkování je nějaká posloupnost levých a pravých závorek a je platné, pokud obsahuje stejně levých jako pravých a v každém prefixu aspoň tolik levých jako pravých. Např. ((())()).
Hint: Catalanova čísla
2
8.2Určete počet un úplných uzávorkování výrazu a1^a2^a3^a4^...^an. Takové uzávorkování přesně určuje v jakém pořadí bude výraz vyhodnocován a každá operace ^ v něm má právě dva operandy. Pořadí operandů v zápise neměníme. Tj. pro a1^a2^a3^a4 jsou úplná uzávorkování a1^((a2^a3)^a4), (a1^a2)^(a3^a4), nebo (a1^(a2^a3))^a4, ale nikoliv třeba (a4^a2)^(a3^a1) a uzávorkování a1^((a2^a3)^a4) a ((a1)^(((a2)^(a3))^(a4))) jsou stejná.
Všimněte si, že, vezmeme-li z výrazu pouze závorky, dostaneme pro první a třetí uzávorkování stejné závorkování (()), takže se nejedná o stejnou úlohu jako 8.1.
Hint: Catalanova čísla
3
8.3Kolik je způsobů, jak rozdělit pravidelný n-úhelník na trojúhelníky pomocí n-3 neprotínajících se úhlopříček?
Hint: Catalanova čísla
3
8.4 Popište všechny dvojice (X,L) takové, že X je neprázdná konečná množina, L je podmnožina P(X) = 2X a platí
  • (P1) pro každé dvě různé p,q z L má jejich průnik velikost právě 1
  • (P2) pro každé dva různé x,y z X existuje právě jedna p z L taková, že x i y náleží p
  • (non P0) Pro každé čtyři různé u,v,w,x z X existuje p z L tak, že |{u,v,w,x} průnik p| je aspoň tři.
Využijte ekvivalentních tvrzení dokázaných na cvičení.
2
9.1Ukažte, že souvislý d-regulární (d ≥ 2) bipartitní graf je
  • a)hranově, nebo
  • b)vrcholově
2-souvislý. (Ukažte a) nebo b).)
2/3
9.2Určete vrcholovou souvislost grafu Kn-Cn,tj. úplného grafu na n vrcholech, z nějž byly odebrány hrany jedné Hamiltonovské kružnice.2
9.3Nechť Qn (n ≥ 1) je orientovaný graf (n-dimenzionální krychle) s množinou vrcholů {0,1}n takový, že z vrcholu u vede orientovaná hrana do vrcholu v právě, když se příslušné vektory liší pouze na jediném místě a na tom má vrchol u nulu a vrchol v jednotku. Položme kapacitu každé hrany 1 a z = (0,0,..,0), s = (1,1,..,1). Najděte
  • a)maximální celočíselný tok v této síti
  • b)maximální tok, který je na všech hranách nenulový.
2+3
10.1Dokažte, že graf na n vrcholech s minimálním stupněm d ≥ (n-1)/2 je hranově d-souvislý.3
10.2Pro n > 3 vezměme n navzájem různých množin A1,A2, . . . ,An, každou o velikosti n-3, jejichž sjednocením je množina X velikosti n. Dokažte, že A1,A2, . . . ,An má systém různých reprezentantů.3
10.3 Dokažte, že CNF-formule, která má v každé klausuli právě n proměnných a každá proměnná se vyskytuje nejvýše n-krát (tzv. (n,≤n)-SAT) je vždy splnitelná.
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. Formule je splnitelná pokud je možno dosadit za proměnné pravdivostní hodnoty tak, aby celá formule byla pravdivá.
4
11.1Hrany úplného grafu na n vrcholech (aspoň dvou) jsou obarveny 2 barvami (červeně a modře). Ukažte, že v grafu existuje jednobarevná kostra.2
11.2Rozhodněte, zda platí: Pro každé obarvení množiny mřížových bodů v rovině (bodů s celočíselnými souřadnicemi) pomocí 2009 barev,
  • a) existuje množina aspoň 2009 celých čísel X, taková, že všechny prvky X x X jsou obarveny stejnou barvou.
  • b)existují dvě množiny aspoň 2009 celých čísel X a Y, takové, že všechny prvky X x Y jsou obarveny stejnou barvou.
2/4 + 2/4
11.3Rozhodněte zda platí: Každý dostatečně velký souvislý graf obsahuje indukovaný podgraf s
  • a) 15i hranami.
  • b) 27i hranami.
6+2
11.4Spočítejte s_n, počet koster žebříku Z_n. Žebřík Z_n je graf, který vznikne ze dvou cest na n vrcholech tak, že spojíme odpovídající si vrcholy n příčkami. Vypadá jako žebřík. Cílem je vzorec v uzavřeném tvaru.5
11.5Spočtěte počet koster grafu K_m,n bez jedné hrany.4

Výsledky


update stránky 29.7.2009

CNW:Counter