![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Strom_-_graf.svg/langcs-640px-Strom_-_graf.svg.png&w=640&q=50)
Strom (graf)
neorientovaný souvislý graf bez kružnic / From Wikipedia, the free encyclopedia
V teorii grafů se jako strom označuje graf, který je souvislý a neobsahuje žádnou kružnici. Lze jej ovšem definovat i dalšími způsoby:
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Strom_-_graf.svg/320px-Strom_-_graf.svg.png)
Následující podmínky pro neorientovaný graf G jsou ekvivalentní:
- G je strom.
- Každé dva vrcholy z G jsou spojeny právě jednou cestou (jednoznačnost cesty).
- G je souvislý a po odebrání libovolné hrany se stane nesouvislým (minimální souvislost).
- G neobsahuje kružnici, ale po přidání libovolné hrany vznikne v G kružnice (maximální graf bez kružnic) .
- G je souvislý a
, kde V je množina vrcholů a E množina hran grafu G.
Stromy mohou být:
- neorientované
- orientované (kořenové)