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.