Kapitola 1
DDÚ Množiny
1. Mějme množiny A = {a, c, d} a B = {b, c, d}. Vypočtěte:
(a) (A C) B) x B
(b) ((A\B) x A) U B
(c) 2A
(d) 2B\2A
(e) (A x A)\(B x B)
Dále udejte příklad prvku množiny A x B, který není prvkem množiny B x A.
2. Definujme množinovou operaci     takto: pro libovolné množiny A a B klademe A + B = (A\B) U (B\Ä).
(a) Slovně popište, co tato operace dělá, tj. jaké prvky leží v množině A^B.
(b) Dokažte, že pro libovolné dvě množiny A, B platí A -z- B = B -z- A.
(c) Čemu se rovná A -z- A, A -z- 0?
(d) Dokažte, že pro libovolné tři množiny A,B,C platí (4 v B) v C = Av(BvC). Čemu se rovná A + B + C?
(e) Obecně, máme-li množiny A\,..., An, čemu se rovná A\    • • • Anl Své tvrzení zdůvodněte.
3. Dokažte platnost následujících tvrzení (A, B, C jsou libovolné množiny):
(a) Jestliže A C B, pak (C\B) C (C\A).
(b) Jestliže AnSnC = 0a zároveň A U B C C, pak A n S = 0.
4. Rozhodněte, zda platí následující tvrzení (A, B, C jsou libovolné množiny). Své rozhodnutí vždy pečlivě zdůvodněte.
1
(a) Jestliže C C A U B, pak (C n A) U (C* n S) = C.
(b) Jestliže (CnA)U(CnB) = C, pak CCiUB.
(c) Jestliže A n S n C = 0, pak některé dvě z množin A, £?, C jsou disjunktní.
(d) Jestliže CCiílB, pak (A\C) n B = 0.
2
Kapitola 2
DDÚ Relace
1. Mějme dány množiny X = {a, b} a Y = {c, d, e} a relace a = {(a, ď), (a, c)} (tedy cr <Z X xY) & p= {(d, b)(e, b), (c, a}} (tj. p C Y x X).
(a) Vypočtěte relace cr-1, p-1, u o p, p o u.
(b) Vypočtěte relaci cr U ((p o cr)-1 o p)-1.
(c) Vypočtěte relaci cr n ((p o cr)-1 o p) 0 p.
2. Na množině {0,1} nalezněte všechny relace, které jsou
(a) reflexivní,
(b) symetrické a zároveň tranzitivní,
(c) symetrické a zároveň antisymetrické.
3. Dejte příklad relace p na množině N takové, že
(a) p je symetrická, tranzitivní, ale není reflexivní,
(b) p není symetrická ani antisymetrická,
(c) p je reflexivní a tranzitivní, ale není symetrická ani antisymetrická,
(d) p není tranzitivní, ale ~ o ~ je tranzitivní,
(e) p není tranzitivní a ani ~ o ~ není tranzitivní.
4. Na množině všech studentů sedících v nějaký okamžik v posluchárně D\ definujme relaci p takto: student A je v relaci se studentem B (tj. (A, B) E p) právě tehdy, když A sedí ve stejné řadě jako B nebo sedí ve stejném sloupci jako B. Rozhodněte, zda je relace p reflexivní, symetrická, tranzitivní či antisymetrická. Je to relace ekvivalence?
5. Rozhodněte a dokažte, zda jsou následující relace ~ na množině celých čísel Z reflexivní, symetrické, tranzitivní či antisymetrické.
(a) a~b^\a\<b
3
(b) a ~ b     a ■ b < O
(c) a ~ b <ŕ=> (a < b a zároveň a ■ 6 > 0)
6. Je množina X rozkladem množiny R?
(a) X = {(a, a + 3) | a je dělitelné 3}
(b) X = {x E R | x3 + (1 - y)x2 - (1 + y)x + y = 0, y E R}
(c) X = {x E R | x3 + (1 - y)x2 + (í-y)x-y = 0, y E R}
(pomůcka: x3 + (1 — y)x2 ± (1 =p y)x =p y = (x2 + x ± l)(x — y))
7. Na množině M = {1, 2, 3,..., 19, 20} je definována relace ~ předpisem a ~ ď <ŕ=> čísla a a ď mají stejný součet cifer. Ověřte, že se jedná o relaci ekvivalence. Popište rozklad M j ~.
8. Na množině Z je definována relace ~ předpisem a ~ 6 <ř=> 2 dělí a2 — b2. Ověřte, že se jedná o relaci ekvivalence. Popište rozklad Z/ ~.
9. Dejte předpis relace ekvivalence ~ na množině p(Z) takové, že rozklad p(Z)/ ~ = {{A | \A\ = j} | j e N0}.
10. Dejte předpis relace ekvivalence ~ na množině M x M takové, že rozklad M x R/ ~ je množina kružnic se středem [0, 0]. (Připomeňme, že rovnice kružnice v rovině dané osami x a y se středem [0, 0] a poloměrem r je x2 + y2 = r2.)
11. Rozhodněte a dokažte, zda jsou následující relace na množině reálných čísel R reflexivní, symetrické, tranzitivní či antisymetrické.
(a) a^b<^>a = b+ l
(b) a~b^ a <b2
(c) a ~ b     a ■ b < 1
12. Najděte maximální, minimální, největší a nejmenší prvky množiny M s uspořádáním p.
(a) M = {a, b, c} a p = {(a, a), (Ď, Ď), (c, c), (a, Ď), (Ď, c), (a, c)}
(b) M = {a, b, c, d} a p = {(a, a), (Ď, b), (c, c), (d, d), (a, Ď), (a, c)}
(c) M = p({a,b}) a p =C
13. Nakreslete všechny hasseovské diagramy na tříprvkové množině.
14. Na R definujeme relaci R předpisem
(x, y) E R       (3c E R)(c > í k c ■ x = y).
Dokažte, že R je uspořádání na R, a naznačte příslušný hasseovský diagram.
4
15. Dejte příklad uspořádané množiny (X, ■<), která
(a) má aspoň dva maximální a aspoň dva minimální prvky
(b) má právě jeden maximální prvek, ale nemá nejmenší prvek
(c) má právě tři minimální prvky a právě jeden nejmenší prvek
(d) obsahuje právě dva nesrovnatelné prvky a nemá žádný maximální ani minimální prvek
16. Je relace -< na množině p({l,2,3} x {u, v}) relace uspořádání?
(a) X -< Y «==^ ((a, b) e Y => (a, b) e X)
(b) X -< Y & \X\ > \Y\
5
Kapitola 3
DDU Zobrazení
1. Najděte všechna zobrazení množiny A = {5, 6, 8} do množiny B = {i, a}. Najděte všechna zobrazení množiny B do množiny A. Která z nich jsou injektivní? Která z nich jsou surjektivní? Která jsou bijekce?
2. Rozhodněte zda daný předpis zadává zobrazení. Pokud zadává zobrazení, určete jestli je injektivní, surjektivní nebo bijekce.
(a) /:Z^(0,l),/(x) = |x|
(0 pro x = 0,
1 prox>l,
2 pro x =< 2
(c) /:Z^N, f(x) = (x - l)2 - 1
(d) /: N-Z,/(*)={;;   P°kud (y-l)2 + l=*,
I L) jinak
(e) f: p(Z)^NU{0}, f(A) = \A\
(f) /: p(N) —>• N, /(A) je minimum A
Upravte zadání předchozích příkladů tak, aby se odpověď změnila; např. změňte výchozí množinu tak, aby zobrazení bylo prosté, cílovou množinu nebo předpis tak, aby bylo surjektivní a pod.
3. Najděte a, b G Z tak, aby zobrazení /: Z —> Z definované předpisem /(x) = |^aa;+bj bylo injektivní nebo surjektivní.
4. Pro bijektivní zobrazení /, g: R —> M, zadané vztahy /(x) = x — 2 a <7(x) = 2x + 3, najděte předpis pro / o g,        g-1 a / o
5. Nechť X = {x, y, z} je množina.
(a) Najděte zobrazení /: X —> X, které není identické a / o / = /.
6
(b) Dejte příklad zobrazení f, g, h: X —> X tak, aby platilo / =/= idx &f°g = g°f&f°h^hof.
6. Nechť A je množina a / : A —> A je zobrazení, které není identické. Dejte příklad zobrazení g, /i: A —> A tak, aby platilo
(a) f °g = g° f,
(b) f o hŕ ho f.
7. Ukažte, že množiny U a V jsou izomorfní (tedy existuje bijekce mezi U a V).
(a) t/ = N, V = N x N. Uvažte zobrazení /: V —> t/ dané předpisem /(x,y) = 2-1(2y-l).
(b) [/ = p(A U B), V = p(A) x p(S), kde A, B jsou libovolné disjunktní množiny. Uvažte zobrazení /: U —>     dané předpisem /(X) = (X n
AinB).
(c) U = R, V = (5,7)
7
Kapitola 4
D D U Výroková logika
1. Nechť P = {a, b,c,...} je množina výrokových symbolů a A, B, C,... jsou výrokové formule. Jedná se v následujících příkladech o výrokové formule? (Pouze v prvním případě jsou uvedeny všechny závorky, které jsou v definici výrokové formule, v dalších případech jsou ponechány pouze nutné závorky.)
(a) ((iAH))VC)
(b) (A —>• a)
(c) (—ip <-> q) A rV —> s
(d) (3A)(3B)(Vc)((AAB)^c)
(e) A -n^B
2. Jaká je valuace výrokové formule A při pravdivostním ohodnocení I: P —> {0,1} daném předpisem P (a) = 1, f (6) = 1, a P(c) = 0?
(a) A = ((-.a A -.c) V (-.c A b)) ->• ((a <-> 6) A -.c)
(b) A = ((-.a V -.c) A (-.c A Ď)) ^ ((a V 6) A c)
3. Rozhodněte, jestli skutečně jsou následující výrokové formule ekvivalentní.
(a) -.(A VBJEniAnB
(b) n(ÍAB) = niv-B,
(c) A —> S = A V      =      —>      (obměna implikace)
4. Nalezněte alespoň dvě různé výrokové formule A dané tabulkou:
8
a	b	c	A
1	1	1	1
1	1	0	0
1	0	1	0
1	0	0	1
0	1	1	1
0	1	0	0
0	0	1	1
0	0	0	1
5. Jsou následující výrokové formule tautologie, kontradikce nebo splnitelné? Existuje výroková formule, která by neměla ani jednu z těchto tří vlastností? (Najděte i v předchozích příkladech tautologie, kontradikce a splnitelné výrokové formule.)
(a) ((AA^B)V {^C AD))     (A V -<C) A (-<B V -<C) A (A V Z?) A (-<B V D)
(b) a —> (b —> a)
(c) (A ^ (B ^ C)) A ^((A -^B)^(A^ C))
6. Nalezněte DNF (disjunktivní normální formu) a CNF (konjunktivní normální formu) pro výrokovou formuli A.
(a) ((A A -.S) V (-.C A D)) A
(b) a^(b^c)
(c) (A—>(B—> C)) A -.A
7. Dokažte, že systém £(l), kde symbol j, značí NOR, je úplný. (Protože z přednášky máte dokázáno, že systém jC(-i,A), resp. jC(-i,V), je úplný, stačí pomocí j, nahradit negaci a konjunkci, resp. negaci a disjunkci. Nicméně zkuste nahradit pomocí j, negaci, konjunkci, disjunkci, implikaci i ekvivalenci. Připomeňme definici: X [Y = ^(X V Y).
Pomocí těchto vztahů přepište výrokovou formuli ^A V ((B —> C) A Z?) do systému
8. Nalezněte ekvivalentní výrokovou formuli v systému C(—<, —>) k formuli (^VB)AC.
9. ** Ukažte, že ani jeden ze systémů C(—<) a £(—>) není úplný.
10. Je teorie T splnitelná? Pokud je odpověď ano, určete zda T \= A a zda T\= B.
(a) T={a->(i)->a),oVř),i),aA ^b}, A =      —>      _B = a —> ->6
(b) T={a^(řna),aVÍ», 6,     A 6}, A =      —>      _B = a —> ->6
(c) T = {(a V -.6) ^c,a^(cV6),nC« 6}, A = (a A 6) V c, B = (cV b) —> a
9
11. ** Pomocí věty o dedukci najděte důkaz výrokové formule.
(a) ^A^A
(b) A ^A
(c) (A^ B) —f {^B ^ -.A)
(d) (-.4    A) —> A
10
Kapitola 5
DDU Predikátová logika
1. Jsou následující formule formulemi predikátové logiky? Pokud jsou, určete, co jsou proměnné, logické spojky, kvantifikátory, rovnost, predikátové symboly a co jsou funkční symboly. U predikátových a funkčních symbolů určete jejich aritu. (Pozor, odpověď se může lišit v závislosti na významu symbolů.)
(a) (Vx)(3y)((3-x = y + l)^x = y2)
(b) a <->
(c) (3x)A(\/y)(P(x,y,x))
(d) (3x)(-i(Vy))(/(x, y, x)), (Např. zde uvažme nejasnost, / můžeme považovat za funkční symbol, ale také za predikátový symbol, zatímco ze zápisu (3x)(-i(Vy))((x, y, x) G /) je zřejmé, že / je predikátový symbol, nicméně tento zápis se často nepoužívá.)
(e) (3y)(\/x)(^B(x, x, x) V C(x, y, y) A (\/z)(U(V(z + z - z)))
(f) (Vx)(x*x)
2. Nalezněte nějakou doménu, ve které je platná formule predikátové logiky ip, a nějakou doménu, ve které platná není.
(a) íf=(Vx)(Vy)(3z)(x + y = z)
(b) ip = (Vx)(Vy)(x H y C {1, 2, 3, 4})
(Povšimněte si, co jsou funkční symboly, co predikátové a jaké je jejich arita.)
3. Přepište následující věty do formulí predikátové logiky. (Nezapomeňte vhodně zvolit doménu.)
(a) Jsou zde pouze studenti IB112.
(b) Všichni studenti a vyučující IB112 jsou zde.
(c) Je právě jeden cvičící IB112.
11
4. Znegujte formuli ip.
(a) V = (Vx)(Z(x) S(x))
(b) V = A Z(x) A ((Vy)(y ^ x) ^ -(L/(y) A Z (y))))
(c) V = P(a, b) V (3x)(P(/(x, x, x) + 5, a * b))
(d) V = (Va;)((5(a;) V U (x)) Z(x))
5. Mějme jazyk £ = { | , *} (bez rovnosti), kde | je binární predikátový symbol a * je binárni funkční symbol. Uvažme interpretaci J\í s doménou N, která | interpretuje jako dělitelnost, tj. a \jj b <ř=> a dělí b, a * interpretuje jako násobení čísel, tj. a *n b = a ■ b. Uvažme ohodnocení V. Platí JV, V \= pl Platí JV \= p? Pokud je odpověď na druhou otázku ne, najděte ohodnocení V takové, že JV, V~ ¥ p.
(a) p = x | y     (V z) (z *x\z*y), V (x) = 5, V (y) = 10, V (z) = 202549
(b) p = x | y ^ (Vz)(z | x * y), V (x) = 3, V (y) = 7
(c) p = (Vx)(Vy)(Vz)((x \ yAy \ z) ^ x \ z), V (x) = 5, V (y) = 356,
= 546582
6. Mějme jazyk C = {<} s rovností, kde < je binární predikátový symbol. Uvažme interpretaci JV, resp. Z, resp. Q jazyka C s doménou N, resp. Z, resp. Q, které interpretují < jako standardní ostré uspořádání. Dejte příklad uzavřené formule p jazyka C tak, že
(a) JV\=p & Z!rp & Q!rp,
(b) N¥ p&Z^p&Qľp,
(c) Af^aZ^a Q N p.
7. Mějme jazyk C = {*} s rovností, kde * je binárni funkční symbol. Uvažme predikátové formule p = x*y = y*x&-ip = (x * y) * z = x * (y * z) tohoto jazyka. Uvažme teorii T = {p}. Platí T \= ip? Je teorie T bezesporná?
8. Dokažte, že teorie U je bezesporná.
(a)
U = {(Vx)(Vy)(Vz)(xEy A x&z <-> xE(ypřz)),
(Vx)(Vy)(Vz)(xĚy V xEz ^ xĚ(yšjz))},
kde E je binární predikátový symbol, pT a sj jsou binární funkční symboly.
(b)
U = {(Vx)(E(x)     (R(x) A S(a;) A T (x))),
(Vx)(R(x)     i?(x.x)),(Va;)(S'(a;) 5(a;«a;)),
(Vx)(T(x)^T(x.x))},
12
kde R, S a T jsou unární predikátové symboly a • je binární funkční symbol.
9. Dokažte, že teorie U je sporná.
U = {(Vx)(\/y)(\/z)((x ■y)-z = x-(y z)),
(Vx)(3t/)(ľ • y = e), (Vx)(e • x = x ■ e), (Vľ)(e = x ■ e),
(3x)(3i/)(-i(x ■ y = y ■ x)), (Vx)(x • x = x)},
kde • je binárni funkční symbol a e je unární funkční symbol.
13
Kapitola 6
DDU Matice a systémy lineárních rovnic
1. Jsou dány matice A = (\ \), B = ( V }2), C = (i §), -D = (-2 V V)-Vypočtěte:
(a) A + B, A + C, B + D, D + 0, 3 • A,
(b) A- B, B ■ A, A- C, B ■ D, C ■ D, D -C, 3 • (C* • D)2.
2. Reste systém lineárních rovnic. (Pozor, ne všechny systémy jsou systémy lineárních rovnic.)
(a)
4x + 2y - 6z = 4 x — 2y — 3z = —5 x + 2y = 1
(b)
3y + 2z = 3 2x - y + 3z = 0 7
3x + 2y + Az=-
(c)
X1X2 + 3aľ3 + 4x4 = 0 x2 + X3X4 = 3 -xi + 14x4 = 0 5xi + x3 = 1
14
(d)
(e)
x\ = 27
(x3 + x4)2 = 9 -xi + x2 + x3 — x4 = O 2x\ + x3 = O
xi + 2x2 + 3aľ3 + 4aľ4 = 1
2ľ2 + X3 + 2ľ4 = 3
-xi + 4x2 + 6x3 + 14aľ4 = O 2xi + x3 = 2
3. Řešte systém lineárních rovnic zadaný maticí.
(a)
(b)
(c)
0 1	3	2 ^		
1 3	2	0		
1 2	1	2		
\ 2 0	1	o J		
/ 1 2	4	-8	-4	1 \
0 2	1	-5	-1	0
1 1	0	-2	0	1
2 0	1	-1	-1	2
\ 3 0	0	0	0	3 í
/ 1	1	1	1	1
3	0	2	0	1
2	1	0	0	0
1	-1	1	-1	1
1	1	3	-1	3
2	-1	0	0	1
-1	1	1	-1 -	-1
V -i	0	1	-1	0
2 \
0 0 0
-1 -1
-2 "2 J
15
Kapitola 7
DDU Kombinatorika a pravděpodobnost
1. V daném školním roce se žáci učí 10 předmětům. Kolika způsoby lze sestavit rozvrh pro třídu na pondělí, jestliže se má v pondělí vyučovat 5 předmětů a žádný předmět nemá být vyučován víckrát ve stejný den?
2. Kolik je všech možných trojciferných čísel?
3. Kolik různých slov (i nesmyslných) lze vytvořit z písmen slova PARDUBICE?
4. V řadě je 5 židlí. Kolika způsoby lze do řady rozesadit 5 žáků, jestliže
2 z nich chtějí sedět vedle sebe?
5. V květinářství prodávají 18 odrůd růží. Kolika způsoby z nich lze vytvořit kytici o 3 květinách?
6. Po skončení večírku se loučí 5 přátel. Kolik stisků ruky si přitom vymění?
7. Na soupisce hokejového týmu je 24 hráčů: 12 útočníků, 10 obránců a 2 brankáři. Kolika způsoby z nich může trenér utvořit sestavu (tj.
3 útočníky, 2 obránce a jednoho brankáře)?
8. Kolik je pěticiferných čísel vytvořitelných z cifer 0,1,4,7,9, v nichž se žádná cifra neopakuje?
9. Kolik různých vrhů (nikoliv součtů) může padnout na dvou různých kostkách? Kolik to bude na dvou stejných kostkách?
10. Jaký je počet a součet všech čtyřciferných čísel z cifer 1, 3, 5, 7, v nichž se žádná cifra neopakuje?
11. Kolik slov (i nesmyslných) lze vytvořit z písmen slova MISSISSIPPI?
16
12. V bridži se hraje s balíčkem z 52 karet, přičemž každý ze 4 hráčů dostane 13 karet. Kolik je možných rozdání?
13. Chceme si objednat zmrzlinový pohár se třemi kopečky, celkem máme na výběr ze sedmi druhů zmrzliny. Kolika způsoby to můžeme udělat?
14. Kolika způsoby lze z 15 chlapců a 12 děvčat vytvořit 4 taneční páry?
15. Profesor bydlící na Manhattanu chodí do práce na univerzitu sídlící tamtéž. Sídlo univerzity se nachází o čtyři ulice severněji a o pět ulic západněji, než je profesorovo bydliště (síť ulic na Manhattanu tvoří klasickou čtvercovou mřížku). Profesor jde do práce vždy nejkratší cestou, tedy nikdy nejde směrem na východ ani na jih a nikdy nepřejde víc na sever či západ, než musí. Kolik různých cest si může zvolit?
16. Házíme 6 kostkami. Jaká je pravděpodobnost, že:
(a) na každé kostce padne jiné číslo,
(b) na všech kostkách padne stejné číslo,
(c) padnou samé šestky,
(d) padne právě pět šestek,
(e) padnou právě čtyři šestky,
(f) padnou alespoň čtyři šestky?
17. Z balíčku 32 karet náhodně vytáhneme 2 karty. Jaká je pravděpodobnost, že první tažená karta má stejnou barvu, jako ta druhá?
18. V urně je 6 koulí očíslovaných od 1 do 6. Postupně koule taháme z osudí a nevracíme je. Jaká je pravděpodobnost, že součet čísel na prvních třech tažených koulích bude alespoň 12?
19. Roztržitý profesor cestou z fakulty navštíví 4 obchody, v každém je pěta-dvacetiprocentní riziko, že v něm zapomene deštník.
(a) Jaká je pravděpodobnost, že zapomene ve čtvrtém obchodě deštník?
(b) Jestliže po návratu domů zjistí, že deštník skutečně někde zapomněl, s jakou pravděpodobností se to stalo ve čtvrtém obchodě?
20. Systém je tvořen dvěma nezávislými bloky, jeden selže s pravděpodobností 0,2 a druhý s pravděpodobností 0, 8. Jaká je pravděpodobnost selhání celého systému, jestliže bloky jsou zapojeny:
(a) sériově,
(b) paralelně?
21. Mějme náhodné jevy A a, B takové, že P (A) = 0, 3, P(B) = 0, 4 a P (A U B) = 0,6. Vypočtěte podmíněné pravděpodobnosti P(A\B), P(B\A) a určete, zda jsou jevy A a B nezávislé.
17
Kapitola 8
DDU Popisná statistika
1. Z jednorozměrného datového souboru známek předmětu IB111 Programování a algoritmizace
/   1 \
2,5
2
3 3
2
3 2 2
V   4 )
utvořte uspořádaný datový soubor. Určete variační obor a rozpětí tohoto datového souboru. Napište vektor variant. Určete absolutní četnost a relativní četnost druhé varianty a absolutní kumulativní četnost a relativní kumulativní četnost prvních tří variant. Sestavte tabulku rozložení četností. Nakreslete polygon, sloupcový diagram a výsečový graf absolutních četností. Spočtěte aritmetický průměr, modus, medián, horní kvar-til, dolní kvartil, rozptyl a směrodatnou odchylku.
2. Pomocí třídících intervalů utvořte roztříděný datový soubor, který udává čas běhu na 100 metrů, daný tabulkou četností:
18
XH)	n{l)
15,5	3
14,0	2
14,7	4
15,4	6
17,2	2
25,0	1
16,7	3
20,0	2
18,4	10
17,4	5
17,6	4
18,0	3
16,4	1
17,9	4
18,1	3
14,2	1
Nezapomeňte napsat tabulku rozložení četností, nakreslit histogram, určit aritmetický průměr, modus medián, horní a dolní kvartil, rozptyl a směrodatnou odchylku.
3. Vypočtěte koeficient korelace mezi platem a počtem dětí daných osob.
plat	počet dětí
8000	3
14000	2
18000	2
20000	0
20000	1
22000	2
26000	2
28000	1
35000	1
38000	2
50000	3
80000	1
19
Kapitola 9
DDU Teorie grafů
1. Nakreslete všechny neizomorfní grafy na šesti vrcholech se čtyřmi hranami.
2. Je následující graf izomorfní s grafem K3 3?
o-o
o-o
3. Dejte příklad dvou grafů na 6 uzlech, které mají stejnou posloupnost stupňů vrcholů, ale nejsou izomorfní. Existují tři takové neizomorfní?
4. Nakreslete graf, který má právě čtyři komponenty souvislosti a nakreslete souvislý graf takový, že po odstranění dvou vrcholů bude mít právě čtyři komponenty souvislosti.
5. Jakou mají hranovou a jakou vrcholovou fc-souvislost grafy C$, K§ a K3 3?
6. Nakreslete dva neizomorfní lesy tvořené 4 stromy stromy, které mají po řadě 1, 2, 3 a 4 listy.
7. Který ze stromů níže je izomorfní kořenovému stromu (kořen vyznačen •). Z toho, který je s ním izomorfní, udělejte kořenový strom tak, aby byly izomorfní jako kořenové stromy.
20
22