MA2BP_CDM1 Cvičeni z diskrétní matematiky 1
8. Stromy, prohledávání grafů
Lukáš Másilko
Středisko pro pomoc studentům se specifickými nároky
Masarykova univerzita
13. 12. 2017
		13. 12. 2017 ]	L/5
MILKOVA - Cvičeni 4.1
1. Rozhodněte, zda posloupnost (1, 1, 1, 1, 2, 3, 3, 4) může být skóre stromu. (Rada: Nejprve zjistěte, zda daná posloupnost je skóre grafu, a pak diskutujte vzájemný vztah mezi počtem vrcholů a hran.)
2. Kolik komponent obsahuje les s 12 vrcholy a 8 hranami?
3. Kolik hran a kolik komponent má les, jehož skóre je (1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4)?
4. Nakreslete všechny podstromy kořenového stromu (T,g) (viz graf na následujícím slajdu) s kořenem ležícím ve třetí vrstvě stromu (T,g).
5. Vyvratte tvrzení: \/G=^VE^ každá hrana grafu G je most =4> G je strom
6. Vyvratte tvrzení: \/G=^VE^ v grafu G platí vztah \ V strom.
E\ + 1     G je
13. 12. 2017
MILKOVA - Cvičeni 4.1
CIENCIALOVI - Neřešené příklady ke kapitole 3
7. Nakreslete graf o sedmi vrcholech, ve kterém existuje pro každé dva vrcholy právě jedna cesta, která je spojuje.
8. Kolik vrcholů stupně 1 může mít strom o dvou a více vrcholech maximálně a kolik minimálně?
22. Je možné, aby v souvislém grafu existovaly dvě různé kostry, jenž nemají žádnou společnou hranu?
Použitá literatura: CIENCIALA, Luděk, CIENCIALOVA, Lucie. Teorie grafů a grafové algoritmy. 1. vyd. Opava, Slezská univerzita v Opavě, 2014. 116 stran. ISBN 978-80-7510-060-3.
13. 12. 2017       4 /5
Prohledání do hloubky a do šírky
Je dán graf na obrázku (viz následující slajd). Pri prohledávání grafu
(a) do šírky,
(b) do hloubky
začněte ve vrcholu s a nalezněte kostru grafu. V obou případech očíslujte pořadí prohledávaných hran a nakreslete příslušný kořenový strom prohledávání.
□
i3P
2017
5/5
Prohledání do hloubky a do šírky