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æ
Fil: Min udsaend trae.svg
Løsningen af minimum udspændende træ problemet kan effektivt findes ved to forskellige algoritmer: Kruskal’s algortime Prim’s algortime
Anvendelse 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.
Kategori:Datalogi Kategori:Grafteori