Det minsta spännträdet (eller minsta spännträdet ) i en (oriktad) sammankopplad viktad graf är spännträdet i denna graf som har minsta möjliga vikt, där vikten av trädet är summan av vikterna av dess kanter.
Problemet med att hitta det minsta spännträdet uppstår ofta i en liknande miljö: anta att det finns n städer som behöver förbindas med vägar så att man kan ta sig från vilken stad som helst till vilken som helst (direkt eller genom andra städer). Det är tillåtet att bygga vägar mellan givna par av städer och kostnaden för att bygga varje sådan väg är känd. Det krävs att man beslutar vilka vägar som ska byggas för att minimera den totala byggkostnaden.
Detta problem kan formuleras i termer av grafteorin som problemet med att hitta det minsta spännträdet i en graf vars hörn representerar städer, kanterna är par av städer mellan vilka en direkt väg kan läggas och kantens vikt är lika stor. till kostnaden för att bygga motsvarande väg.
Det finns flera algoritmer för att hitta det minsta spännträdet. Några av de mer kända är listade nedan:
Steinerträdsproblemet liknar problemet med minsta spännträd . Den innehåller flera punkter på planet och det är nödvändigt att lägga en graf över banor mellan dem på ett sådant sätt att summan av väglängder minimeras. Huvudskillnaden från problemet med minsta spännträd i detta fall är att det är tillåtet att lägga till ytterligare grenpunkter för att ytterligare minska summan av kantlängder. Steinerträdsproblemet är NP-komplett .
| Algoritmer för grafsökning | ||
|---|---|---|
| Oinformerade metoder | ||
| Informerade metoder | ||
| Genvägar | ||
| Minsta spännträd | ||
| Övrig | ||