PLIN006 cvičení, jaro 2011
Př. 1
Nakreslete grafy a určete stupně jednotlivých vrcholů:
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {{1, 2}, {1, 4}, {2, 3}, {3, 4}, {2, 4}}
∙ 𝑉 = {𝑤, 𝑥, 𝑦, 𝑧}, 𝐸 = {{𝑤, 𝑥}, {𝑥, 𝑦}, {𝑦, 𝑧}}
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {{1, 2}}
∙ 𝑉 = {1, 2}, 𝐸 = ∅
∙ 𝑉 = ∅, 𝐸 = ∅
Které z nich jsou souvislé, které z nich jsou stromy? Vyjádřete tyto grafy jako
relace.
Př. 2
Nakreslete a zapište množinovým zápisem následující grafy:
∙ úplný graf na 4 vrcholech
∙ úplný graf na 3 vrcholech
∙ úplný graf na 2 vrcholech
∙ úplný graf na 1 vrcholu
∙ úplný graf na 6 vrcholech
∙ kružnici na 6 (resp. 5, 4, 3, 2, 1) vrcholech
∙ cestu na 6 (resp. 5, 4, 3, 2, 1) vrcholech
∙ graf, který má stupně vrcholů postupně 2, 3, 3, 2
∙ graf, který má stupně vrcholů postupně 3, 3, 4, 4, 4
∙ graf, který má stupně vrcholů postupně 2, 4, 4, 2
Najděte v těchto grafech největší kliky, největší cykly a nejdelší cesty.
1
PLIN006 cvičení, jaro 2011
Př. 3
Které z následujících grafů jsou izomorfní? Najděte isomorfismy, případně
určete, proč grafy izomorfní nejsou.
Př. 4
Najděte nejdelší cesty a cykly v následujících grafech:
2
PLIN006 cvičení, jaro 2011
Př. 5
Nakreslete následující orientované grafy:
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {(1, 2), (1, 4), (2, 3), (3, 4), (2, 4)}
∙ 𝑉 = {𝑤, 𝑥, 𝑦, 𝑧}, 𝐸 = {(𝑤, 𝑥), (𝑥, 𝑦), (𝑧, 𝑦), (𝑤, 𝑧)}
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {(1, 2)}
∙ 𝑉 = {1, 2}, 𝐸 = ∅ Najděte v těchto grafech největší cykly a nejdelší
cesty.
Př. 6
V následujících grafech najděte minimální kostry a nejkratší cesty mezi
vybranými dvojicemi vrcholů. Nejprve „selským rozumem”, poté použijte
Kruskalův a Dijkstrův algoritmus.
3
PLIN006 cvičení, jaro 2011
Př. 7
V orientovaném grafu z předchozího cvičení najděte silně souvislé kompo-
nenty.
Př. 8
Naprogramujte Kruskalův a Dijkstrův algoritmus v Pythonu.
Př. 9
Zapište v jazyce logiky vlastnosti, které musí splňovat pravděpodobnostní
rozložení.
Př. 10
Vyjádřete funkčním zápisem a grafem rozložení pravěpodobnosti při hodu
kostkou.
Př. 11
Mějme následující statistický soubor (výška lidí ve skupině):
160, 160, 160, 170, 170, 180, 180, 180, 190, 210
Nakreslete graf pravděpodobnostního rozložení výšky lidí na základě tohoto
souboru. Jaká je pravděpodobnost, že člověk bude vyšší než 185?
4
PLIN006 cvičení, jaro 2011
Nakreslete graf distribuční funkce pro statistický soubor výše.
Př. 12
Hážeme dvakrát po sobě kostkou. Poprvé padlo 5. Jaká je pravděpodobnost,
že padne součet větší než 8? Použijte vzorec podmíněné pravděpodobnosti.
Př. 13
Mějme následující údaje o skupině lidí:
ID Výška (cm) Váha (kg)
1 180 80
2 170 90
3 190 60
4 190 80
5 180 80
6 190 90
Mějme člověka, o kterém víme, že měří 190 cm. Jaká je pravděpodobnost,
že jeho váha bude alespoň 80 kg? (Předpokládejme, že naše data jsou
reprezentativní. (Kterému zákonu tento náš předpoklad odporuje?))
Př. 14
Dokažte Bayesův vzorec.
Př. 15
Všichni chlapci nosí kalhoty, polovina dívek nosí také kalhoty (druhá
polovina nosí sukně :) ). Vidíme z dálky člověka, který má kalhoty. Jaká je
pravděpodobnost, že je to chlapec?
Př. 16
Mějme následující text a předpokládejme, že pro dané účely je to reprezentativní
vzorek:
Stát má stát na straně pro stát vhodné. Stát na straně občanů je pro stát
obvykle nevýhodné. Nicméně stát by se mohl stát poctivějším.
Jaká je pravděpodobnost, že slovo „stát” (bez rozlišení velikosti písmen)
je sloveso (podst. jméno), pokud:
5
PLIN006 cvičení, jaro 2011
∙ neuvažujeme žádnou informaci o kontextu
∙ slovo „stát” stojí na začátku věty
∙ předchozí slovo je předložka
∙ následující slovo obsahuje právě dvě písmena
Př. 17
Máme podezření, že hrací kostka není vyvážená, ale že na ní častěji padají
šestky. Máme v úmyslu kostku sérií 20 pokusů vyzkoušet. Kolikrát musí
padnout šestka, aby se naše podezření statisticky potvrdilo s možností chyby
méně než 1 %?
6