Pravolinijsko razapinjuće stablo
U teoriji grafova, pravolinijsko minimalno razapinjuće stablo (PMRS) u skupu od n tačaka u ravan (ili uopštenije u–ℝd). je minimalno razapinjuće stablo, gde je težina ivica između dve tačke pravolinijska udaljenost između te dve tačke.
Osobine i algoritmi uredi
Planaran slučaj uredi
Ovaj članak je nedovršen. |
Stavke uredi
Elektronski dizajn uredi
Problem obično nastaje u fizičkom dizajnu elektronskih kola. Dužina žice između dve tačke se prirodno meri pravolinijski. Iako umrežavanje bolje predstaviti sa razapinjućim Stejnerovim stablom, PMRS obezbeđuje razumnu približnu procenu dužine žica.[1]
Reference uredi
- ^ F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal of Applied Mathematics, 30:104–114, 1976.