În matematică, un arbore spanning este un subgraf al unui grafic nedirecționat care include toate nodurile grafului nedirecționate. Este un instrument fundamental folosit pentru a rezolva probleme dificile în matematică, cum ar fi problema cu patru culori și problema vânzătorului călător. De obicei, un copac spanning format din ramificația de la unul din punctele interioare, motiv pentru care este descris ca un copac.

Explicatie detaliata

Pentru a vizualiza un copac spanning, imaginați mai întâi un grafic nedirecționat: de exemplu, o colecție aleatorie de puncte conectate prin linii. Conexiunile trebuie să fie nedirecte; ceea ce înseamnă că puteți călători în ambele direcții pe linii pentru a ajunge de la un punct la altul. Fiecare punct trebuie să fie conectat la restul într-un fel și fiecare punct poate avea mai multe conexiuni.

Un arbore care acoperă acest grafic este orice subgraf (un grafic care utilizează aceleași puncte) care atinge toate punctele, deși nu are nevoie să împartă toate aceleași linii.

Grafic, termeni de rețea, protocol Spanning Tree