Корисник:Dragan25/Pesak

У теорији графова, праволинијско минимално разапињуће стабло (ПМРС) у скупу од н тачака у раван (или уопштеније у–ℝ^д). је минимално разапињуће стабло, где је тежина ивица између две тачке праволинијска удаљеност између те две тачке.

Properties и алгоритми

Applications

Електронски дизајн

Проблем обично настаје у физичком дизајну електронских кола. У модерним густим високо интегрисаним колима wire routing is performed by wires which consist of segments running horizontally in one layer of metal and vertically in another metal layer. Као резултат, дужина жице између две тачке се природно мери праволинијски. Иако умрежавање боље представити са разапињућим Стејнеровим стаблом, ПМРС обезбеђује разумну приближну процену дужине жица.

References

Шаблон:Comp-sci-theory-stub