strom (graf)

V teorii grafu se jako strom oznacuje neorientovaný graf, který je souvislý a neobsahuje žádnou kružnici. Lze jej ovšem definovat i dalšími zpusoby:
Následující podmínky pro neorientovaný graf G jsou ekvivalentní:

1. G je strom.
2. Každé dva vrcholy z G jsou spojeny práve jednou cestou (jednoznacnost cesty).
3. G je souvislý a po odebrání libovolné hrany se stane nesouvislým (minimální souvislost).
4. G neobsahuje kružnici, ale po pridání libovolné hrany vznikne v G kružnice (maximální graf bez kružnic) .
5. G je souvislý a , kde V je množina vrcholu a E množina hran grafu G.