Centrum wykresu - Graph center

Wykres z centralnymi punktami w kolorze czerwonym. Są trzy wierzchołki  taki, że d ( ,  B ) ≤ 3 dla wszystkich wierzchołków  B . Każdy czarny wierzchołek znajduje się w odległości co najmniej 4 od innego wierzchołka.

Centrum (lub Jordan środkowa) z wykresu jest zbiorem wszystkich wierzchołków co najmniej mimośród , który jest zbiorem wszystkich wierzchołków U gdzie największa odległość d ( u , v ) do pozostałych wierzchołków V jest minimalne. Równoważnie jest to zbiór wierzchołków o mimośrodzie równym promieniowi wykresu . W ten sposób wierzchołki w środku ( punkty środkowe ) minimalizują maksymalną odległość od innych punktów na wykresie.

Jest to również znane jako problem wierzchołków 1-centrum i może być rozszerzony na problem wierzchołków k-centrum .

Znalezienie środka wykresu jest przydatne w problemach z lokalizacją obiektu, gdzie celem jest zminimalizowanie najgorszej odległości od obiektu. Na przykład umieszczenie szpitala w centralnym punkcie skraca najdłuższą odległość, jaką musi pokonać karetka.

Centrum można znaleźć za pomocą algorytmu Floyda-Warshalla . Zaproponowano inny algorytm oparty na rachunku macierzowym.

Pojęcie środka grafu wiąże się z miarą bliskości w analizie sieci społecznościowych , która jest odwrotnością średniej odległości d ( A , B ).

Bibliografia

  1. ^ B Wasserman, Stanley i Fausta, Katherine (1994), Analiza Sieci Społecznych: Methods and Applications , strona 185. Cambridge: Cambridge University Press. ISBN  0-521-38269-6
  2. ^ McHugh, James A., Algorytmiczna teoria grafów zarchiwizowano 01.08.2010 w Wayback Machine
  3. ^ Weisstein, Eric W. „Centrum wykresu” . MatematykaŚwiat .
  4. ^ Floyd, Robert W. (czerwiec 1962). „Algorytm 97: najkrótsza ścieżka”. Komunikaty ACM. 5 (6): 345 https://doi.org/10.1145/367766.368168
  5. ^ Warshall, Stephen (styczeń 1962). „Twierdzenie o macierzach Boole'a”. Dziennik ACM. 9 (1): 11–12 https://doi.org/10.1145/321105.321107
  6. ^ "Nowy algorytm obliczania środka grafu i podziału grafu według odległości od środka" . Październik 2019.