Centrum wykresu - Graph center
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
- ^ 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
- ^ McHugh, James A., Algorytmiczna teoria grafów zarchiwizowano 01.08.2010 w Wayback Machine
- ^ Weisstein, Eric W. „Centrum wykresu” . MatematykaŚwiat .
- ^ Floyd, Robert W. (czerwiec 1962). „Algorytm 97: najkrótsza ścieżka”. Komunikaty ACM. 5 (6): 345 https://doi.org/10.1145/367766.368168
- ^ Warshall, Stephen (styczeń 1962). „Twierdzenie o macierzach Boole'a”. Dziennik ACM. 9 (1): 11–12 https://doi.org/10.1145/321105.321107
- ^ "Nowy algorytm obliczania środka grafu i podziału grafu według odległości od środka" . Październik 2019.