Diskrétní matematika (NMIN105)

Pre informácie o predmete Kombinatorika (NMAG403) kliknite sem.

Na tejto stránke je možné nájsť všetky informácie k cvičeniam z Diskrétnej matematiky (NMIN105), ktoré sa konajú každý štvrtok o 10:40, resp. 12:20 v učebni M5, resp. M2 na Karlove. Prednáška k tímto cvičeniam sa koná každý štvrtok o 9:00 v posluchárni M1 na Karlove. Prednášajúcim je prof. Martin Loebl. Cvičiacim je RNDr. Marek Tesař a v prípade, že by ste na mňa mali akékoľvek otázky, napíšte mi mail na tesar"zavinac"kam.mff.cuni.cz, prípadne ma pri istej dávke šťastia môžete zastihnúť na Malej Strane, číslo dverí 125.

Na získanie zápočtu bude treba v priebehu semestra získať 60 bodov. Body sa dajú získavať rôznymi spôsobmi. V priebehu semestra budú dve písomky, každá po 40 bodov. Body sa ďalej dajú získavať riešením domácich úloh (ktoré môžete nájsť nižšie) a aktivitou na cvičení (počet bodov závisí na zložitosti príkladu). Posledným spôsobom ako sa budú dať získať body je dochádzka. Každý, kto v priebehu semestra vymešká maximálne tri cvičenia, dostane automaticky 10 bodov (za každú absenciu navyše príde o 3 body).

Domáce úlohy sa odovzdávajú v papierovej forme. Deadline na odovzdanie je štandardne nastavený na 3 týždne (môžete teda odovzdávať príklady, ktorých deadline je zelený alebo oranžový). Znamená to, že budete mať teda čas na to, aby ste každú úlohu odovzdali 2 krát (v prípade, že ste na prvýkrát nezískali maximálny možný počet bodov). Upozorňujem, že na konci sesmestra sa tento termín môže skrátiť, z dôvodu toho, že sa nebudem nachádzať v Prahe.

Cvičenie: Deadline: Príklad: Zadanie: Body:
3.10.
24.10.
1.1
Nech P,Q a R sú výroky. Zistite, či je nasledujúci výrok tautológia:
((P ∧ Q) ⇒ R) ⇔ (¬R ⇒ (¬P ∨ ¬Q))
2
10.10.
31.10.
2.1
Dokážte indukciou, že 12+22+ 32+ ... + n2 = n(n+1)(2n+1)/6.
2
10.10.
31.10.
2.2
Dokážte indukciou, že 4 | (6n2 + 2n) (4 delí 6n2 + 2n), pre každé n prirodzené.
1
10.10.
31.10.
2.3
Majme šachovnicu o rozmeroch 2n x 2n pre n prirodzené, na ktorej chýba jedno rohové políčko. Dokážte, že túto šachovnicu vieme vydláždiť s dlaždičkami nasledujúceho tvaru (dlaždičky môžeme aj otáčať):
3
17.10.
14.11.
3.1
Nech X = {-23, -22, ..., 186} a nech množina Y vznikne z množiny X tak, že z nej vyškrtáme všetky násobky čísel 6,9,15,18,27,30. Zistite, koľko prvkov obsahuje množina Y.
2
17.10.
14.11.
3.2
O prirodzenom čísle n povieme, že je square-free, ak n nie je delitelné číslom k2, pre žiadne k ≥ 2 prirodzené. Zistite koľko square-free čísel sa nachádza v intervale 30, 31, ..., 250.
2
17.10.
21.11.
3.3
Pomocou vhodnej kombinatorickej interpretácie a použitím princípu inklúzie a exklúzie spočítajte nasledujúcu sumu pre n, m, j prirodzené a n ≤ j ≤ m + n (t.j. vyjadrite túto sumu ako nejaký výraz, ktorý už viac nebude obsahovať sumu)
4
24.10.
21.11.
4.1
Použitím algebraickej definície kombinačného čísla dokážte, že každé kombinačné číslo je celé a nezáporné.
2
24.10.
21.11.
4.2
Nájdite všetky n také, že výraz (2n | n) je delitelný číslom 4 (kde (a | b) značí kombinačné číslo a nad b).
3
24.10.
21.11.
4.3
Nech n je prirodzené číslo delitelné 4. Spočítajte sumu:
(n | 0) - (n | 2) + (n | 4) - (n | 6) +... + (n | n)
kde (a | b) značí kombinačné číslo a nad b.
2
31.10.
5.12.
5.1
Relácia (X,R) na množine X môže splňovať tri základné vlastnosti: reflexivitu, tranzitivitu a symetriu. Pre každú reláciu R máme teda 8 možností podľa toho, ktoré z týchto vlastností spĺňa a ktoré nespĺňa. Pre každú takúto kombináciu vlastností (spĺňa - nespĺňa), uvedte príklad relácie (spolu 8 rôznych relácií) spĺňajúcu práve danú kombináciu vlastností (pokiaľ daná relácia neexistuje, tak to dokážte).
2
31.10.
5.12.
5.2
Majme dve ekvivalencie (X,R) a (X,S) na množine X. Zistite, či sú potom aj nasledujúce relácie nutne ekvivalencie: (X, R ∪ S), (X, R ∩ S) a (X, R / S) (používame operácie zjednotenia, prieniku a rozdielu).
2
31.10.
5.12.
5.3
Zistite, či existuje nekonečná postupnosť funkcií f1, f2, f3, ... z prirodzených čísel do prirodzených čísel taká, že pre všetky k platí, že fk+1 = O(fk) a fk nie je v O(fk+1) (t.j. nekonečná asymptoticky ostro klesajúca postupnosť funkcií).
2
21.11.
12.12.
6.1
Nech n, k a m sú prirodzené čísla. Zistite, koľko existuje usporiadaných k-tic (a1, a2, .., ak) prirodzených čísel takých, že pre všetky i = 1,2, .., k je ai ≥ m a a1 + a2 + .. + ak = n.
3
21.11.
12.12.
6.2
Zistite, ktoré z grafov na nasledujúcom obrázku sú navzájom izomorfné, alebo dokážte, že izomorfné nie sú.
2
21.11.
12.12.
6.3
Z definície izomorfizmu dokážte, že ak G a H sú dva izomorfné grafy, tak aj ich doplnky G' a H' sú izomorfné (doplnok grafu je graf na rovnakej množine vrcholov a hrana medzi vrcholmi vedie vtedy a len vtedy ak táto hrana neexistovala v pôvodnom grafe).
2
21.11.
12.12.
6.4
Nech G a H sú dva (n-2)-regulárne grafy na n vrcholoch (graf je k-regulárny ak všetky jeho vrcholy majú stupeň práve k). Dokážte, že potom G a H sú izomorfné. Bude toto tvrdenie platiť, aj pre (n-3)-regulárne grafy G a H?
2
28.11.
19.12.
7.1
Dokážte, že každý jednoduchý graf (t.j. neorientovaný, bez slučiek a násobných hrán) s aspoň 2 vrcholmi, obsahuje dva vrcholy rovnakého stupňa.
2
28.11.
19.12.
7.2
Pre ktoré nezáporné celé číslo x je postupnosť (1,1,2,3,5,5,x) skóre nejakého grafu? Pričom pokiaľ hodnoty v tejto postupnosti nie sú neklesajúce, tak si ich najprv príslušne zotriedte. Pre príslušné x nájdite aj príklad takého grafu.
2
28.11.
19.12.
7.3
Nech T je strom na n > 1 vrcholoch a nech di značí počet vrcholov grafu T stupňa i. Dokážte, že potom platí:
d1 - d3 - 2.d4 - .. - (n-2).dn = 2
2
5.12.
2.1.
8.1
Nech 1 ≤ d1 ≤ d2 ≤ ... ≤ dn je postupnosť celých čísiel splňujúca d1 + d2 + ... + dn = 2n - 2. Dokážte, že existuje strom na n vrcholoch, ktorý má skóre (d1, d2, ... , dn).
2
5.12.
2.1.
8.2
V grafe G nazveme podmnožinu V' vrcholov grafu G, že je nezávislá ak podgraf indukovaný na vrcholoch V' neobsahuje žiadne hrany. Dokážte, že v každom strome na n vrcholoch existuje nezávislá množina, ktorá obsahuje aspoň polovicu vrcholov.
2
5.12.
2.1.
8.3
Nájdite maximálny a tiež minimálny možný počet hrán jednoduchého grafu, ktorý má práve n vrcholov a práve k komponent súvislosti. Všetky svoje tvrdenia zdôvodnite!
2
5.12.
2.1.
8.4
Nech G je 2-súvislý graf. Dokážte, že pre každé dve rôzne hrany e a f grafu G existuje kružnica, ktorá obsahuje obidve hrany.
2
12.12.
9.1.
9.1
Nech G je Eulerovský graf. Dokážte, že hrany grafu G sa dajú rozdeliť do niekoľkých disjunktných kružníc (cyklov).
2
12.12.
9.1.
9.2
Nech G = (V,E) je 2k-regulárny súvislý graf. Dokážte, že hrany grafu G sa dajú rozdeliť do dvoch množín A a B tak, aby grafy (V, A) a (V, B) boli k-regulárne vtedy a len vtedy ak k*|V| je sudé (párne) číslo.
2
12.12.
9.1.
9.3
Spočítajte počet kostier tohoto grafu:
2
12.12.
9.1.
9.4
Použitím vzorca (pre počet kostier) K(G) = K(G\e) + K(G "kontrakcia" e) dokážte, že počet kostier úplného grafu na 4 vrcholoch je 42.
1
19.12.
16.1.
10.1
Spočítajte počet kostier úplného bipartitného grafu Km,n.
2
19.12.
16.1.
10.2
Nech graf G vznikne z úplného grafu Kn odstránením jednej hrany. Spočítajte počet kostier grafu G.
2
9.1.
16.1.
11.1
Dokážte, že nasledujúci graf na 8 vrcholoch nie je rovinný:
2
9.1.
16.1.
11.2
Dokážte, že pre n>4 každé nakreslenie úplného grafu Kn do roviny obsahuje aspoň (n | 4) / 5 priesečníkov (kde (a | b) značí kombinačné číslo a nad b).
3
9.1.
16.1.
11.3
Označme Gn graf n-dimenzionálnej kombinatorickej kocky (krychle), t.j. vrcholy budú n-prvkové vektory (v1, v2, ... vn) núl a jedničiek a medzi dvoma vrcholmi v a w vedie hrana práve vtedy, ak sa tieto vektory líšia v práve jednej súradnici. Nájdite všetky n, pre ktoré je graf Gn rovinný.
3
9.1.
16.1.
11.4
Dokážte, že grafy K6, K7, K4,4 a Petersenov graf sa dajú nakresliť na torus (kúpacie koleso) bez kríženia hrán. (Doporučujem si v skriptách doštudovať spôsob, že čomu odpovedá kreslenie na torus).
4
9.1.
16.1.
11.5
Dokážte, že neexistuje graf G na 11 vrcholoch taký, že G aj doplnok grafu G sú rovinné (doplnok grafu je graf na rovnakej množine vrcholov a hrana medzi vrcholmi vedie vtedy a len vtedy ak táto hrana neexistovala v pôvodnom grafe).
2

Ak som na cvičení spomínal domácu úlohu, ktorá sa nenachádza v tomto zozname, dajte mi prosím čo najskôr vedieť..