Grafikon medián

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. április 3-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A medián a gráf azon csúcsa , amelynél a gráf csúcsai közötti legrövidebb távolságok összege a lehető legkisebb.

Legyen szükség a telefonközpont, az elektromos alállomás, az úthálózatban ellátó bázisok, vagy a postai szolgáltató osztályozó részleg elhelyezésére. Mindezen létesítmény-elhelyezési problémák esetén ezt a létesítményt úgy kell elhelyezni, hogy az ettől a létesítménytől a gráf csúcsaiig tartó legrövidebb távolságok összege a lehető legkisebb legyen. A pont adott értelemben vett optimális elhelyezkedését a grafikon mediánjának nevezzük.

A p-medián probléma

Egy adott gráf p-mediánjának megtalálásának problémája egy adott számú (mondjuk p) létesítmény elhelyezésének problémája úgy, hogy a gráf csúcsai és a legközelebbi létesítmények közötti legrövidebb távolságok összege a lehető legkisebb értéket vegye fel. . $G$ $G$

gráf p-mediánja

Általánosítsuk a medián fogalmát a p-medián definiálásával .

Legyen egy irányított gráf X csúcskészletének részhalmaza , és tegyük fel, hogy p csúcsot tartalmaz. Újradefiniáljuk a következő jelölést: $X_{p}$ $G=(X,\Gamma )$ $X_{p}$

$d(X_{p},x_{j})=min[d(x_{i},x_{j})]$

$d(x_{j},X_{p})=min[d(x_{j},x_{i})]$ , ahol mindenek felett a minimumot keresik . ${\displaystyle x_{i}\in X_{P))$

Ha egy csúcs -ból van , amelynél az előző képletekben elérjük a minimumot, akkor azt mondjuk, hogy a csúcshoz kapcsolódik . $x_{i}^{1}$ $X_{p}$ $x_{j}$ $x_{i}^{1}$

A csúcsok halmazának áttételi arányait hasonlóképpen határozzuk meg, mint egyetlen csúcs áttételi arányait: $X_{p}$

$\sigma _{o}(x_{i})=\sum v_{j}d(X_{p},x_{j})$ - külső áttétel ,

$\sigma _{t}(x_{i})=\sum v_{j}d(x_{j},X_{p})$ - belső áttétel .

Azt a halmazt , amelyre a minimumot keresik , a gráf külső p-mediánjának nevezzük , a belső p-mediánt pedig hasonlóképpen definiáljuk. $X_{o}^{*}$ $\sigma _{o}(X_{o}^{*})=min[\sigma _{o}(x_{i})]$ $X_{p}\subseteq X)$ $G$

Abszolút p-medián

A feladat leegyszerűsítése érdekében továbbgondolunk egy irányítatlan G gráfot . Ekkor a "t" és az "o" indexek hiányoznak, mivel a külső és belső áttételek egybeesnek. Azt a grafikonpontot (csúcspont vagy ívpont), amelynél az áttétel a legkisebb értéket veszi fel, a G gráf abszolút mediánjának nevezzük.

Irodalom

Christofides N. Gráfelmélet. Algoritmikus megközelítés. - M .: Mir, 1978.
E. Mainik. Optimalizálási algoritmusok hálózatokhoz és gráfokhoz. — M .: Mir, 1981. — 324 p.

Grafikon medián

A p-medián probléma

gráf p-mediánja

Abszolút p-medián

Irodalom

Linkek