I matematikk er et spennende tre en undergraf av en ikke-rettet graf som inneholder alle de ikke-rettede grafens hjørner. Det er et grunnleggende verktøy som brukes til å løse vanskelige problemer i matematikk, for eksempel firefargekartproblemet og det reisende selgerproblemet. Vanligvis er et spenningstreet dannet ved å forgrene seg ut fra en av de indre punktene, og derfor beskrives det som et tre.

Detaljert forklaring

For å visualisere et spennende tre, første bilde en ukjent graf: for eksempel en tilfeldig samling av punkter koblet med linjer. Tilkoblingene må være utelukkende; noe som betyr at du kan reise i begge retninger på linjene for å komme fra ett punkt til et annet. Hvert punkt må være koblet til resten på en eller annen måte, og hvert punkt kan ha flere tilkoblinger.

Et spennende tre for denne grafen er noen subgraph (en graf som bruker de samme punktene) som berører alle punktene, selv om det ikke trenger å dele alle de samme linjene.

Graf, Nettverksvilkår, Spanning Tree Protocol