Grafcentrum - Graph center

En graf med centrala punkter färgade rött. Dessa är de tre hörn  En sådan att d ( A ,  B ) ≤ 3 för alla hörn  B . Varje svart vertex är ett avstånd på minst 4 från någon annan toppunkt.

Det centrum (eller Jordanien centrum) av en kurva är den uppsättning av alla hörn av minsta excentricitet , dvs den uppsättning av alla vertex u där det största avståndet d ( u , v ) till andra hörn v är minimal. På motsvarande sätt är det uppsättningen hörn med excentricitet lika med grafens radie . Således minimerar hörn i mitten ( centrala punkter ) det maximala avståndet från andra punkter i grafen.

Detta är också känt som vertex 1-center-problemet och kan utvidgas till k-center-problemet .

Att hitta mitten av en graf är användbart vid problem med anläggningsplatser där målet är att minimera det värsta avståndet till anläggningen. Att placera ett sjukhus på en central punkt minskar till exempel ambulansens längsta sträcka.

Centret kan hittas med Floyd – Warshall -algoritmen . En annan algoritm har föreslagits baserat på matrisberäkning.

Begreppet mitten av en graf är relaterat till närhetscentralitetsmåttet i sociala nätverksanalyser , vilket är det ömsesidiga medelvärdet för avstånden d ( A , B ).

Referenser

  1. ^ a b Wasserman, Stanley och Faust, Katherine (1994), Social Network Analysis: Methods and Applications , sidan 185. Cambridge: Cambridge University Press. ISBN  0-521-38269-6
  2. ^ McHugh, James A., Algorithmic Graph Theory Arkiverad 2010-08-01 på Wayback Machine
  3. ^ Weisstein, Eric W. "Grafcentrum" . MathWorld .
  4. ^ Floyd, Robert W. (juni 1962). "Algoritm 97: Kortaste väg". Kommunikation av ACM. 5 (6): 345 https://doi.org/10.1145/367766.368168
  5. ^ Warshall, Stephen (januari 1962). "Ett teorem om booleska matriser". Journal of the ACM. 9 (1): 11–12 https://doi.org/10.1145/321105.321107
  6. ^ "En ny algoritm för beräkning av grafcentrum och grafpartitionering enligt avståndet till mitten" . Oktober 2019.