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
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:
Anvendelse redigér
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.