Korisnik:Dragan25/Pesak
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.
Properties i algoritmi[uredi | uredi izvor]
Planaran slučaj[uredi | uredi izvor]
Applications[uredi | uredi izvor]
Elektronski dizajn[uredi | uredi izvor]
Problem obično nastaje u fizičkom dizajnu elektronskih kola. U modernim gustim visoko integrisanim kolima wire routing is performed by wires which consist of segments running horizontally in one layer of metal and vertically in another metal layer. Kao rezultat, 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]
References[uredi | uredi izvor]
- ^ F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal of Applied Mathematics, 30:104–114, 1976.