グラフの中心

中心点が赤色のグラフ。これらは、すべての頂点 *Bに対して*d ( A , B ) ≤ 3となる3 つの頂点Aです。各黒い頂点は、他の頂点から少なくとも 4 の距離にあります。

グラフの中心（またはジョルダン中心^[1]）は、最小離心率^[2]のすべての頂点の集合、つまり、他の頂点vまでの最大距離d（u、v）が最小となるすべての頂点uの集合です。同様に、グラフの半径に等しい離心率を持つ頂点の集合です。^[3]したがって、中心の頂点（中心点）は、グラフ内の他の点からの最大距離を最小化します。

これは頂点 1 中心問題としても知られており、頂点 k 中心問題に拡張できます。

グラフの中心を見つけることは、施設への最悪の距離を最小化することを目標とする施設配置問題に役立ちます。たとえば、病院を中心点に配置すると、救急車が移動しなければならない最長距離が短縮されます。

中心はフロイド・ワーシャルアルゴリズムを使用して見つけることができます。^[4]^[5]行列計算に基づく別のアルゴリズムが提案されています。^[6]

グラフの中心の概念は、ソーシャルネットワーク分析における近接中心性の尺度に関連しており、これは距離d ( A、B )の平均の逆数である。^[1]

参考文献

^ ab Wasserman, Stanleyおよび Faust, Katherine (1994)、Social Network Analysis: Methods and Applications 、185 ページ。ケンブリッジ : Cambridge University Press。ISBN 0-521-38269-6
^ McHugh, James A., Algorithmic Graph Theory 2010-08-01 にアーカイブされたWayback Machine
^ Weisstein, Eric W.「グラフ中心」。MathWorld。
^ フロイド、ロバート W. (1962 年 6 月)。「アルゴリズム 97: 最短経路」。Communications of the ACM。5 (6): 345 https://doi.org/10.1145/367766.368168
^ ウォーシャル、スティーブン（1962年1月）。「ブール行列の定理」ACMジャーナル9（1）：11–12 https://doi.org/10.1145/321105.321107
^ 「グラフ中心の計算と中心までの距離に応じたグラフ分割のための新しいアルゴリズム」。2019年10月。

[WF-1] Wasserman, Stanleyおよび Faust, Katherine (1994)、Social Network Analysis: Methods and Applications 、185 ページ。ケンブリッジ : Cambridge University Press。ISBN 0-521-38269-6

[2] McHugh, James A., Algorithmic Graph Theory 2010-08-01 にアーカイブされたWayback Machine

[3] Weisstein, Eric W.「グラフ中心」。MathWorld。

[4] フロイド、ロバート W. (1962 年 6 月)。「アルゴリズム 97: 最短経路」。Communications of the ACM。5 (6): 345 https://doi.org/10.1145/367766.368168

[5] ウォーシャル、スティーブン（1962年1月）。「ブール行列の定理」ACMジャーナル9（1）：11–12 https://doi.org/10.1145/321105.321107

[P-6] 「グラフ中心の計算と中心までの距離に応じたグラフ分割のための新しいアルゴリズム」。2019年10月。