Grafteori: Vandringer og stier

Hva er et tre?

Et tre er en sammenhengende graf uten sykler.

• Det finnes bare en sti mellom hvert par av noder.
• Hvis en kant fjernes, blir grafen ikke sammenhengende.
• Hvis en kant legges til, får grafen en sykel.
• Antall kanter er én mindre enn antall noder.