Udspændende træ (grafteori)

En delgraf T af en graf G, hvor T forbinder alle knuderne i grafen G således at der højst findes en vej mellem to forskellige knuder, kaldes for et udspændende træ. Delgrafen T er sammenhængende og acyklisk (kredsløs), derfor er T pr. definition et træ.

Et interessant problem er at finde det såkaldte minimum udspændende træ i en given graf, dvs. et udspændende træ hvor summen af vægtene på de forskellige kanter i træet er minimal. Mere præcist kan problemet defineres således: Lad G = (V,E) være en ikke orienteret vægtet graf med knude mængden V og kant mængden E, hvor hver kant forbinder to knuder fra mængden V, dvs. (u, v) ∈ E. Lad w(u, v) betegne den funktion der til enhver kant (u, v) ∈ E, angiver kantens vægt. Vi ønsker at finde en acyklisk delmængde T ⊆ E som forbinder alle knuderne i grafen og hvis total vægt givet ved

${\displaystyle w(T)=\sum _{(u,v)\in T}^{}w(u,v)}$

er minimeret.

Et eksempel på en graf samt dens minimum udspænende træ

Løsningen af minimum udspændende træ problemet kan effektivt findes ved to forskellige algoritmer:

• Kruskal’s algortime
• Prim’s algortime

Minimum udspændende træ problemet bliver eksempelvis brugt indenfor elektronik. Her ønsker man at designe et elektrisk kredsløb, således at n komponenter i kredsløbet bliver forbundet med hinanden ved brug af n – 1 ledninger, hvor hver ledning forbinder to komponenter. Man er som regel interesseret i den løsning der bruger den mindst mulige mængde af ledninger.