Písemná zkouška z Diskrétní matematiky 4. 1. 2015 (1. termín)
Jméno a příjmení	1	2	3	4	5	Součet
						
Každý příklad je hodnocen 16 body. Pro odpovědi využijte volného prostoru mezi příklady. Test trvá 100 minut.
1. Nechť X = {0,1,2} je množina a A C "P(X) systém jejích podmnožin. Pro každou z následujících formulí nalezněte nějaký systém, který formuli splňuje a nějaký systém (ten v odpovědi označte jako £>), který ji nesplňuje. Pokud takový A nebo B neexistuje, dokažte to.
a) (VX, Y G A) (X H {0,1} = Y n {0,1}       X = Y).
b) (y x, y e A) (x c f v ľa).
c) (Var, y G X)(3F G .A) ((x Gľ A y^Y) V (x^ľAi/e F)).
d) (VYeA)(X-YeA).
2. Sestrojte (nebo dokažte, že neexistuje)
a) nějaké surjektivní izotonní zobrazení /:(P(N),C)->(7>({1,2,3,4}),C),
b) nějaký izomorfismus uspořádaných množin g:(V({l,2,3A}),C)^(V({l,2,3A}),D).
3. Nechť R, S, T jsou relace na množině X. Dokažte, že platí: a) (R o S'1)'1 = SoR-\
b) (R U S) o T = (R o T) U (S o T).
4. Načrtněte všechny vzájemně neizomorfní grafy s pěti vrcholy a šesti hranami.
5. a) Určete počet permutací (tj. bijekcí na sebe) n-prvkové množiny A, které splňují (\/x G ä){f {x) ý x) (tj- nemají pevný bod).
b) Určete počet maximálních párování úplného bipartitního grafu km<n. (Připomeňme, že párování je podgraf, jehož žádné dvě hrany nemají společný vrchol.)
Řešení
1. a) Formule říká, že všechny množiny systému A „jsou rozlišovány" průnikem s {0,1}. Můžeme tedy vzít třeba A = {{0},{1}}, ale stačilo by i A = 0. B musí obsahovat nějaké množiny lišící se právě prvkem 2, tedy například B = {{0}, {0,2}} nebo rovnou B = V(X).
b) Formule říká, že všechny množiny systému A jsou porovnatelné inkluzí. Vezmeme třeba A = 0, B = V(X).
c) Chceme, aby pro libovolné dva prvky systém obsahoval množinu, která z těchto prvků obsahuje jen jeden ale ne druhý. Prvky x,y jsou libovolné, může se tedy stát, že x = y. Pak je ovšem žádnou množinou oddělit nelze, systém A dané vlastnosti tedy neexistuje. B lze zvolit libovolně, např. B = 0.
d) S každou množinou chceme mít v ^4. i její doplněk v X. Zvolíme třeba A = V(X),B = {{0}}.
2. a) Nejpřirozenější je za / vzít zobrazení, které z každé podmnožiny N vyhodí všechny prvky různé od 1, 2, 3 nebo 4, tedy
f(X)=Xn {1,2,3,4}.
Snadno nahlédneme, že / zachovává inkluzi a je tedy izotonní. Každá podmnožina {1, 2, 3,4} je obrazem sebe sama, / je tedy také surjektivní.
b) Hledáme bijekci, která otáčí uspořádání. Nejjednodušší způsob je zobrazit každou podmnožinu na její doplněk, tj.
g(X) = {1,2,3,4} -X.
Protože doplněk doplňku je původní podmnožina, g je sama k sobě inverzní, a je to tedy bijekce. Stačí se už jen přesvědčit, že X C Y implikuje {1,2,3,4} — Y C {1,2,3,4} - X, tedy g = g-1 je izotonní.
3. a)
(R o S
SoR
-i
{(x	y)	(y, x	) G R o S'1}
{(x	y)	(3z)	[(y,z) e S'1 A (z,x) e R)}
{(x	y)	(3z)	[(z, y) E S A (z, x) E R)},
{(x	y)	(3z)	[(x, z) E R'1 A (z, y) E S)}
{(x	y)	(3z)	[(z,x) E R A (z,y) E S)}.
b)
(R U S) o T	= {(x	y)	(3z)	[(x, z)	G T A (z,y) e RUS)}
	= {(x	y)	(3z)	{(x, z)	G T A ((z,y)ER V (z,y)eS)}
	= {(x	y)	(3z)	{((x, z	) G T A (z,y) G i?) V ((x,^) G T A (z, y) E S))},
(i? o T) U (S o T)	= {(x	y)	(x,y	) G R	oT V (x, y) E S o T}
	= {(x	y)	(3z)	{(x, z)	e T A(z,y)eR) v A(^)e5)}
	= {(x	y)	(3z)	{((x, z	)GT A (2, y) G i?) V ((v)GT A (z, y) G S*))}.
4.
Grafy nejsou izomorfní, neboť si ve většině případů neodpovídají stupně všech vrcholů (tzv. skóre grafu). Jediná dvojice se stejným skórem je 4. a 6. graf, ty rozlišíme např. pozorováním, že 3. graf má kružnici délky 3, zatímco 6. graf ji nemá. Pokud předpokládáme, že dolní vrchol má být vrchol s nejnižším stupněm, snadno nahlédneme, že dalším přesunem hran už nedostaneme jiná řešení.
5. a) Úloha je variantou „šatnářky". K řešení použijeme princip inkluze a exkluze. Dostáváme součet
(0)n!" (1)(""1)! + (2)(" - 2>! - " ■ +    Q (" - ">! =
i=Q v /
Přitom 2-tý sčítanec odpovídá odhadu počtu permutací s i pevnými body (ty se vybírají kombinačním číslem a zbylé libovolně permutujeme).
b) Úplný bipartitní graf km,n má všechny hrany mezi m-prvkovou „levou" podmnožinou vrcholů a jejím n-prvkovým „pravým" doplňkem. Poněvadž
žádný vrchol se nemůže účastnit více než jedné hrany párování, budou v maximálním párování zastoupeny všechny prvky menší z podmnožin a do páru k nim vybrány libovolné ale různé prvky větší z podmnožin. Budeme tedy počítat variace. Pro m <n dostáváme n(n—l)(n — 2)... (n — m+1) = („"^p pro n < m by to bylo analogicky , m! v.