Корисник: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. Као резултат, дужина жице између две тачке се природно мери праволинијски. Иако умрежавање боље представити са разапињућим Стејнеровим стаблом, ПМРС обезбеђује разумну приближну процену дужине жица.[1]
References[уреди | уреди извор]
- ^ F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal of Applied Mathematics, 30:104–114, 1976.