S6: Acyklické grafy - stromy
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 Kn, aby sme dostali strom?6. Nájdite centrum stromu T1 a T2.
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
- 26 februára 2016, 00:09
- 26 februára 2016, 00:09