Kaavion mediaani

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 3. huhtikuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Mediaani on graafin kärki , jolle lyhimpien etäisyyksien summa siitä graafin kärkipisteisiin on pienin mahdollinen.

Olkoon tarpeen valita paikka puhelinvaihteen, sähköaseman, tieverkon syöttöpisteiden tai postin lajitteluosaston sijoituspaikaksi. Kaikissa näissä laitoksen sijaintiongelmissa tämä laitos on sijoitettava siten, että lyhimpien etäisyyksien summa tästä toiminnosta graafin kärkipisteisiin on mahdollisimman pieni. Pisteen optimaalista sijaintia esitetyssä mielessä kutsutaan graafin mediaaniksi.

P-mediaaniongelma

Ongelma tietyn graafin p-mediaanin löytämisessä on ongelma paikantaa tietty määrä (esimerkiksi p) toimintoja siten, että graafin pisteistä lähimpiin tiloihin lyhimpien etäisyyksien summa on pienin mahdollinen arvo. . $G$ $G$

kaavion p-mediaani

Yleistetään mediaanin käsite määrittämällä p-mediaani .

Olkoon suunnatun graafin kärkijoukon X osajoukko ja oletetaan, että se sisältää p pistettä. Määrittelemme seuraavan merkinnän uudelleen: $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})]$ , jossa kaikessa tavoitellaan minimiä . ${\displaystyle x_{i}\in X_{P))$

Jos on kärkipiste alkaen , jossa minimi saavutetaan edellisissä kaavoissa, niin huippupisteen sanotaan olevan kiinnitettynä . $x_{i}^{1}$ $X_{p}$ $x_{j}$ $x_{i}^{1}$

Piikkijoukon välityssuhteet määritellään samalla tavalla kuin yksittäisen kärjen välityssuhteet: $X_{p}$

$\sigma _{o}(x_{i})=\sum v_{j}d(X_{p},x_{j})$ - ulkoinen välityssuhde ,

$\sigma _{t}(x_{i})=\sum v_{j}d(x_{j},X_{p})$ - sisäinen välityssuhde .

Joukkoa , jonka minimiä haetaan kaikista , kutsutaan graafin ulkoiseksi p-mediaaniksi ja sisäinen p-mediaani määritellään samalla tavalla. $X_{o}^{*}$ $\sigma _{o}(X_{o}^{*})=min[\sigma _{o}(x_{i})]$ $X_{p}\subseteq X)$ $G$

Absoluuttinen p-mediaani

Tehtävän yksinkertaistamiseksi tarkastellaan edelleen suuntaamatonta kuvaajaa G. Tällöin indeksit "t" ja "o" puuttuvat, koska ulkoinen ja sisäinen välityssuhde ovat samat. Kuvaajan pistettä (kärkipiste tai kaaripiste), jonka välityssuhde saa pienimmän arvon, kutsutaan kuvaajan G absoluuttiseksi mediaaniksi .

Kirjallisuus

Christofides N. Graafiteoria. Algoritminen lähestymistapa. - M .: Mir, 1978.
E. Mainik. Optimointialgoritmit verkoille ja kaavioille. - M .: Mir, 1981. - 324 s.

Kaavion mediaani

P-mediaaniongelma

kaavion p-mediaani

Absoluuttinen p-mediaani

Kirjallisuus

Linkit