V matematiki je spanning drevo podgraf neusmerjenega grafa, ki vključuje vsa neusmerjena vozlišča grafa. To je temeljno orodje, ki se uporablja za reševanje težavnih matematičnih problemov, kot so problemi s štirimi barvami in problem prodajalca. Običajno se razprostira iz enega od notranjih točk, zato se opisuje kot drevo.

Podrobna razlaga

Za vizualizacijo raztezajočega drevesa najprej prikažite neusmerjeni graf: na primer naključno zbiranje točk, povezanih s črtami. Povezave morajo biti neusmerjene; kar pomeni, da lahko potujete v obe smeri na linijah, da pridete od ene točke do druge. Vsaka točka mora biti nekako povezana z ostalimi, vsaka točka pa ima lahko več povezav.

Spanning drevo za ta graf je katerikoli podgraf (graf, ki uporablja iste točke), ki se dotakne vseh točk, čeprav ni treba deliti vseh istih vrstic.

Graf, omrežni izrazi, protokol Spanning Tree