Každý student musí napsat referát z předmětu Diskrétní matematika sám, žádná spolupráce na textu referátu není dovolena. Je pouze povoleno diskutovat o zadání referátu se spolužáky i na cvičeních.

V každém referátu jsou dva příklady, jeden z kombinatoriky, druhý z teorie grafů. Hodnotí se každý příklad 0/5/10 bodů, tj. stylem NE/TÉMĚŘ SPRÁVNĚ/ANO. V případě mimořádně kvalitního řešení příkladu lze udělit i 15 bodů. Referát vypracujte formou odborného článku: nadpis, jméno, abstrakt a přehledné členění na sekce. Bude psán na počítači v rozsahu asi 2 až 5 stran A4. Referát odevzdáváte e-mailem v předepsaném formátu nebo na papíře příslušnému vyučujícímu (kontakt je uveden u každého zadání). Cvičící vás může vyzvat k přednesení vašeho referátu během cvičení.

Abstrakt je odstavec shrnující o čem referát je a co je hlavním přínosem vaší práce. Zahrnuje i podstatu zadání. Zadání referátu nekopírujte do výsledného textu, ale vlastními slovy v úvodu popište co jste řešili.

Číslo zadání bude studentům přiděleno na cvičení.

1. Zadání

Kombinatorika
Máte k dispozici 10 stokorun, 10 tisícikorun a dvě osudí (krabice), do kterých není vidět. Soutěž probíhá tak, že soutěžící si vybere jedno osudí a vylosuje z něj náhodně jednu bankovku. Jak rozdělit bankovky do osudí (v každém osudí je alespoň jedna bankovka), aby průměrná výhra byla co největší? Dokažte!

Teorie grafů
Acyklický graf se nazývá les. Nechť F_n je les s k komponentami. Dokažte, že počet hran F_n je n-k.

2. Zadání

Kombinatorika
Nalezněte co největší k∈ N tak, aby p^k dělilo n!, přičemž p je prvočíslo.

Teorie grafů
Najděte všechny grafy G na 2n vrcholech takové, že nejmenší stupeň grafu je n-1 a současně G je nesouvislý. Dokažte, že Váš seznam je úplný.

3. Zadání

Kombinatorika

Teorie grafů
Dokažte následující větu. Jestliže má strom T úplné párování, pak pro každý vrchol v∈V(T) platí, že graf T-v má jedinou lichou komponentu. Lichou komponentou rozumíme komponentu, která má lichý počet vrcholů.

4. Zadání

Kombinatorika
Nechť A je n prvková množina.
a) Kolik různých antisymetrických relací na této množině existuje?
b) A kolik různých symetrických relací, které nejsou reflexivní, na A existuje?
Návod: Uvažujte kolik máme možností pro každou dvojici uspořádaných dvojic (x,y), (y,x), x≠y a pro každou uspořádanou dvojici (x,x).

Teorie grafů
Dokažte, že je-li pro daný graf δ(G)≥2, potom G obsahuje cyklus.

5. Zadání

Kombinatorika
Zaveďme funkci r(n), která udává nejvyšší řád permutace na n prvcích. Ukažte, že r(n) je neklesající. Dále ukažte, že r(n) není rostoucí.

Teorie grafů
Určete χ(W_n) pro libovolné n≥3. χ(G) je barevnost grafu, tedy takový nejmenší počet barev, pro který existuje dobré vrcholové barvení grafu G. W_n je graf na n+1 vrcholech, který vznikne z cyklu C_n přidáním vrcholu v₀ a hran z v₀ do všech vrcholů cyklu C_n.

6. Zadání

Kombinatorika
Mějme balíček karet očíslovaných 1, 2, ..., 32. Představme si, že máme stroječek na míchání karet. Když do stroječku vložíme seřazený balíček v pořadí 1, 2, ..., 32, strojek balíček rozdělí na dvě poloviny a zamíchá tak (udělá takovou permutaci karet), že vmíchá karty z jedné poloviny (prvních 16 karet) mezi karty druhé poloviny. Dostaneme tak pořadí 1, 17, 2, 18, 3, 19, ..., 16, 32. Jaký je řád permutace, neboli po kolika nejméně opakovaných mícháních dostaneme opět seřazený balíček?

Teorie grafů
Supermagické ohodnocení grafu G je takové očíslování hran grafu G čísly {1, 2, ..., |E(G)|} (každé použité právě jedenkrát), že pro každý vrchol v∈V(G) je součet ohodnocení hran incidentních s vrcholem v roven stejnému číslu k (tzv. magická konstanta).
Ukažte, že graf K₈ nemá supermagické ohodnocení.
Návod: Určete magickou konstantu grafu K₈.
Umíte výsledek zobecnit?

7. Zadání

Kombinatorika
Hážeme n šestistěnnými kostkami. Jaká je pravděpodobnost, že součet hozených hodnot bude lichý?
Návod: Uvědomte si, že součet hodnot na protilehlých stěnách kostky je 7, tedy liché číslo. Potom zkuste najít (existuje-li) nějaké jednoznačné přiřazení, jak libovolnému hozenému sudému součtu přiřadit součet lichý a naopak.

Teorie grafů
Máme pravidelný bipartitní graf s partitami U aW a alespoň jednou hranou. Ukažte, že |U| = |W|.

8. Zadání

Kombinatorika
Máte k dispozici tři kuličky s číslem 1, dvě kuličky s číslem 2, jednu kuličky s číslem 3 a tři osudí (krabice), do kterých není vidět. Soutežící si vybere jedno osudí a vylosuje z něj náhodně jednu kuličku. Jak rozdělit kuličky do osudí (v každém osudí je alespoň jedna kulička), aby průměrné tažené číslo bylo co nejmenší? Dokažte!

Teorie grafů
Kolik různých grafů G s n vrcholy existuje, pokud G nemá žádný izolovaný vrchol? Pod pojmem "různé grafy" budeme rozumět takové grafy, které nemají totožné hranové množiny, neboť všechny grafy budeme konstruovat na téže n-prvkové vrcholové množině.
Návod: Stanovme V(G) = {v₁,v₂,... ,v_n}. Množina G_i nechť je množina všech grafů, kde je vrchol v_i izolovaný. Dále stanovme, kolik existuje všech různých grafů G s n vrcholy. Pak použijte princip inkluze a exkluze.

9. Zadání

Kombinatorika
Kolik existuje různých vyplněných sudoku 4×4? Jinými slovy kolika způsoby můžeme vyplnit čísly 1,2,3,4 čtverec obsahující 4×4 políček, tak aby každý sloupec a řádek obsahoval každou číslici právě jednou? Navíc je čtverec rozdělen na čtyři stejné podčtverce 2×2, které rovněž musí obsahovat každou číslici právě jednou.

Teorie grafů
Dokažte, že pokud existují v grafu dva liché cykly, které mají alespoň jednu společnou hranu, existuje pak v grafu také sudý cyklus.

10. Zadání

Kombinatorika
Dokažte, že součet třetích mocnin každých tří po sobě jdoucích přirozených čísel je dělitelný devíti.

Teorie grafů
Průměr grafu je vzdálenost dvou nejvzdálenějších vrcholů v grafu. Dokažte nebo vyvraťe, že následujícím postupem získáme průměr libovolného stromu T.
Vezmeme libovolný vrchol v∈T a najdeme k němu nejvzdálenější vrchol w. Poté nalezneme k vrcholu w nejvzdálenější vrchol u. Pak diametr stromu T je roven vzdálenosti mezi vrcholy w a u.
Návod: Vytvořte ze stromu T kořenový strom s kořenem v centru c. Větví kořenového stromu T rozumíme každou komponentu grafu T-c. Délka větve je délka cesty z vrcholu c do nejvzdálenějšího vrcholu větve. Ukažte, že cesta z libovolného vrcholu v∈V(T) do nejvzdálenějšího vrcholu ve stromu T vede přes centrum c.

11. Zadání

Kombinatorika
Na ples přišlo n manželských párů. Kolika způsoby lze vytvořit vždy n tanečních párů tak, aby žádní manželé netančili spolu?
Návod: Označme jednotlivé manželské páry p₁, p₂, ..., p_n. Množina P_i nechť je množina všech tanečních párů, kde pár p_i tančí spolu. Dále stanovme, kolik existuje všech možných tanečních párů. Pak použijte princip inkluze a exkluze.

Teorie grafů
Dokažte, že je-li ve stromu T_n vrchol stupně k, tak v T existuje alespoň k vrcholů stupně 1.

12. Zadání

Kombinatorika
Kolik existuje pořadí písmen A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P, z nichž vypuštěním některých písmen nemůžeme získat ani jedno ze slov DOBA, COP, OPICE? Například ze slova ABCDEFGHIJKLMNOP lze vynecháním písmen získat slova COP, ale DOBA a OPICE ne.

Bonus 1

Kombinatorika
Eulerova funkce φ přiřazuje každému přirozenému číslu n počet všech kladných přirozených čísel, která jsou menší než n a jsou nesoudělná s n, tedy φ(n)=|{ m : m∈ {1, 2,...,n} a současně nsd(m,n)=1}|.

Určete φ(n) pro n = p₁^{n₁}p₂^{n₂}p₃^{n₃}, kde p_i je prvočíslo a n_i∈ N pro každé i = 1,2,3.
(Návod: Zkuste úkol nejdříve vyřešit pro n=p a n=p^m, kde p je prvočíslo a m∈ N. Použijte princip inkluze a exkluze.)

Bonus 2

Teorie grafů
Pro každé 1≤a≤b≤c∈N najděte příklad grafu, který má vrcholový stupeň souvislosti a, hranový stupeň souvislosti b a nejmenší stupeň c.

Náhradní referát

Kombinatorika
Trenér fotbalového družstva má k dispozici o obránců, z záložníků a u útočníků, kde o,z,u ∈ N, o,z,u≥4. Dále k záložníků, k∈ N, 3 ≤ k ≤ z, může hrát i v útoku. Kolik různých sestav může trenér vytvořit, pokud hraje systém 4-3-3, tedy 4 obránci, 3 záložníci, 3 útočníci?

Teorie grafů
Nechť každé dva cykly v souvislém cyklickém grafu G mají nejvýše jeden společný vrchol. Najděte vztah mezi počtem koster tohoto grafu a délkami jednotlivých cyklů.
Návod: Označte si délky cyklů například m₁,m₂,... ,m_k pro k≥1 a dokažte, že pokud dva cykly C a C' nemají žádný společný vrchol, pak existuje jediná dvojice vrcholů u∈ C, v∈ C' taková, že v G existuje přesně jedna (u,v)-cesta. Tento fakt vám napoví jaká je struktura grafu.

Mnoho zdaru při řešení samostatného referátu!

Poznámka

Pokud najdete v textu zadání chybu, dejte mi, prosím, vědět. Pokusím se chyby co nejdříve opravit.