Mediana graficului

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 3 aprilie 2018; verificările necesită 2 modificări .

Mediana este vârful graficului pentru care suma celor mai scurte distanțe de la acesta la vârfurile graficului este minimă posibilă.

Să fie necesar să alegeți un loc pentru amplasarea unui central telefonic, a unei substații electrice, a bazelor de alimentare într-o rețea de drumuri sau a unui departament de sortare într-un serviciu poștal. În toate aceste probleme de localizare a instalației, este necesar să se localizeze această facilitate în așa fel încât suma celor mai scurte distanțe de la această facilitate la vârfurile graficului să fie cât mai mică posibil. Locația optimă a punctului în sensul indicat se numește mediana graficului.

Problema p-mediană

Problema găsirii p-medianei unui grafic dat este problema localizării unui număr dat (să zicem, p) de facilități astfel încât suma celor mai scurte distanțe de la vârfurile graficului la cele mai apropiate facilități să ia valoarea minimă posibilă. . $G$ $G$

p-mediana unui grafic

Să generalizăm conceptul de mediană prin definirea p-mediană .

Fie o submulțime a mulțimii de vârfuri X a unui graf direcționat și presupunem că acesta conține p vârfuri. Redefinim următoarea notație: $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})]$ , unde se cauta minimul peste toate . $x_{i}\in X_{P)$

Dacă este un vârf din , la care se atinge minimul în formulele anterioare, atunci se spune că vârful este atașat la . $x_{i}^{1}$ $X_{p}$ $x_{j}$ $x_{i}^{1}$

Raporturile de transmisie ale unui set de vârfuri sunt definite în mod similar cu rapoartele de transmisie ale unui singur vârf: $X_{p}$

$\sigma _{o}(x_{i})=\sum v_{j}d(X_{p},x_{j})$ - raport de transmisie extern ,

$\sigma _{t}(x_{i})=\sum v_{j}d(x_{j},X_{p})$ - raportul de transmisie intern .

Mulțimea pentru care (se caută minimul peste toate ) se numește p-mediana externă a graficului , iar p-mediana internă este definită în mod similar. $X_{o}^{*}$ $\sigma _{o}(X_{o}^{*})=min[\sigma _{o}(x_{i})]$ $X_{p}\subseteq X)$ $G$

p-mediană absolută

Pentru a simplifica sarcina, vom lua în considerare în continuare un grafic nedirecționat G. Atunci indicii „t” și „o” vor fi absenți, deoarece rapoartele de transmisie externe și interne vor coincide. Punctul grafic (punctul de vârf sau arc), pentru care raportul de transmisie va lua cea mai mică valoare, se va numi mediana absolută a graficului G.

Literatură

Christofides N. Teoria grafurilor. Abordare algoritmică. — M .: Mir, 1978.
E. Mainik. Algoritmi de optimizare pentru rețele și grafice. — M .: Mir, 1981. — 324 p.

Mediana graficului

Problema p-mediană

p-mediana unui grafic

p-mediană absolută

Literatură

Link -uri