|
Strom alebo stromový graf je grafické vyjadrenie členenia určitej množiny na jej podmnožiny (napr. súbory na podsúbory, strojársky výrobok na podskupiny a súčiastky a pod.). Graf okrem členenia znázorňuje aj postupnosť členenia alebo zlučovania. Spojenie jednotlivých vetiev stromu ukazuje zlúčenie (delenie), pričom dĺžkou vetví môže vyjadriť hladinu, na ktorej sa podskupiny zlučujú (delia).
Strom je neprázdny súvislý graf, ktorý neobsahuje kružnicu (cyklus). Na označenie stromov, ako špeciálnych grafov, sa používa označenie T = (V, H). Písmeno T je z anglickej terminológie (tree – strom).
Les je jednoduchý graf bez kružníc, ktorého komponentami sú stromy.
Strom, ktorý má každej hrane priradený jeden z dvoch možných smerov, sa nazýva orientovaný strom.
Strom možno definovať:
- G je strom.
- Každé dva vrcholy z G sú spojené práve jednou cestou (jednoznačnosť cesty).
- G je súvislý a po odobraní ľubovoľnej hrany sa stane nesúvislým (minimálna súvislosť).
- G neobsahuje kružnicu, ale po pridaní ľubovoľnej hrany vznikne v G kružnica (maximálny graf bez kružníc) .
- G je súvislý a
 , kde V je množina vrcholov a E množina hrán grafu G.
celý článok...
|
