Rättlinjigt minimumspännande träd
I grafteorin är det rätlinjiga minsta spännträdet ( RMST ) för en uppsättning av n punkter i planet (eller mer allmänt, i ℝ d ) ett minsta spännträd i den uppsättningen, där vikten av kanten mellan varje par av punkter är det rätlinjiga avståndet mellan dessa två punkter.
Egenskaper och algoritmer
Genom att explicit konstruera den fullständiga grafen på n hörn, som har n ( n -1)/2 kanter, kan ett rätlinjigt minimumspännande träd hittas med hjälp av befintliga algoritmer för att hitta ett minimumspännande träd. I synnerhet ger användning av Prims algoritm med en närliggande matris tidskomplexitet O( n2 ) .
Planar fall
I det plana fallet finns det effektivare algoritmer. De är baserade på idén att anslutningar endast får ske med närmaste granne till en punkt i varje oktant - det vill säga vart och ett av de åtta områdena i planet som avgränsas av koordinataxeln från denna punkt och deras bisektrar.
Den resulterande grafen har bara ett linjärt antal kanter och kan konstrueras i O( n log n ) med hjälp av en dividera och erövra-algoritm eller en sveplinjealgoritm .
Ansökningar
Elektronisk design
Problemet uppstår ofta i fysisk design av elektroniska kretsar . I moderna integrerade kretsar med hög densitet utförs ledningsdragning av ledningar som består av segment som löper horisontellt i ett metallskikt och vertikalt i ett annat metallskikt . Som ett resultat mäts trådlängden mellan två punkter naturligt med rätlinjigt avstånd. Även om routingen av ett helt nät med flera noder representeras bättre av det rätlinjiga Steinerträdet , ger RMST en rimlig approximation och uppskattning av trådlängden.