Vybrané kapitoly z diskrétnej matematiky

1.      Ktoré tvrdenia sú pravdivé

a)      Počet hrán stromu je rovný počtu vrcholov.

b)      Strom má o jednu hranu viac , než vrcholov.

c)      Počet hrán v strome je vždy menší než počet vrcholov.

d)      Dva rôzne stromy s rovnakým počtom vrcholov musia mať vždy rovnaký počet hrán.

2. Nakreslite 6 rôznych stromov, ktoré budú obsahovať 6 vrcholov.

3. Nakreslite 3 kostry Petersenovho grafu.

4. V databáze je 12 záznamov a 34 väzieb medzi nimi. Keby sme chceli vytvoriť štruktúru databázy znázornenú pomocou grafu, tak:

a)      Bude takýto graf strom?

b)      Bude takýto graf súvislý?

5. Koľko hrán musíme vynechať z grafu K_n, aby sme dostali strom?

6. Nájdite centrum stromu T₁ a T₂.

7. Ukážte, že súvislý graf má jediný komponent.

8. Dokážte, že všetky kostry daného grafu majú rovnaký počet hrán.

9. Dokážte: centrum kružnice sa rovná vrcholovej množine.

10. Dokážte: ak cesty  majú spoločné koncové body, tak z ich hrán možno vybrať kružnicu, ktorej dĺžka nepresahuje súčet dĺžok ciest