Праволинијско разапињуће стабло
Изглед
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0c/Rectilinear_minimum_spanning_tree.svg/300px-Rectilinear_minimum_spanning_tree.svg.png)
У теорији графова, праволинијско минимално разапињуће стабло (ПМРС) у скупу од н тачака у раван (или уопштеније у–ℝд). је минимално разапињуће стабло, где је тежина ивица између две тачке праволинијска удаљеност између те две тачке.
Особине и алгоритми[уреди | уреди извор]
Планаран случај[уреди | уреди извор]
![]() | Овај чланак је недовршен. |
Ставке[уреди | уреди извор]
Електронски дизајн[уреди | уреди извор]
Проблем обично настаје у физичком дизајну електронских кола. Дужина жице између две тачке се природно мери праволинијски. Иако умрежавање боље представити са разапињућим Стејнеровим стаблом, ПМРС обезбеђује разумну приближну процену дужине жица.[1]
Референце[уреди | уреди извор]
- ^ F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal of Applied Mathematics, 30:104–114, 1976.