Праволинијско разапињуће стабло

Из Википедије, слободне енциклопедије
Rectilinear minimum spanning tree.svg

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

Особине и алгоритми[уреди]

Планаран случај[уреди]

Wiki letter w.svg Овај чланак, или један његов део, треба још да се прошири.
Погледајте страну за разговор за разлог. Када се побољшавање заврши, можете склонити ово обавештење.

Ставке[уреди]

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

Проблем обично настаје у физичком дизајну електронских кола. Дужина жице између две тачке се природно мери праволинијски. Иако умрежавање боље представити са разапињућим Стејнеровим стаблом, ПМРС обезбеђује разумну приближну процену дужине жица.[1]

Референце[уреди]

  1. ^ F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal of Applied Mathematics, 30:104–114, 1976.