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 | uredi izvor]
Planaran slučaj[uredi | uredi izvor]
 | Ovaj članak je nedovršen. |
Stavke[uredi | uredi izvor]
Elektronski dizajn[uredi | uredi izvor]
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 | uredi izvor]
- ^ F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal of Applied Mathematics, 30:104–114, 1976.