グラフのeccentricity(離心性)と半径(radius)と直径(diameter)と中心(center)とその他

参考サイト
説明
- Connected graphを考える
- Eccentricityは個々のノードに定義される
  - あるノード $n_i$ について、 $n_i$ 以外のすべてのノード $n_k(k￥not=i)$ について、グラフ上の最短距離を求める(グラフ上の最短距離は、エッジに長さが与えられていなければ、エッジ数に同じ)
  - 今、このようにして得られたすべての最短距離のうち、最長のものをこのノードのeccentricityと定義する
- Center
  - Eccentricityがグラフ中最小のノードをCenter(中心)と呼ぶ。定義からわかるとおり、１つとは限らない
- 半径(radius)と直径はグラフについて定義される
  - 今、すべてのノードのeccentricityについて、その最小値を半径、その最大値を直径とする
- その他の指標
  - $H$ も $￥Delta$ もグラフ理論上の呼称を見つけられないが・・・
  - グラフがcenterを中心に「まとまりがよいか＝centerから多方向にひろがっているか」の指標とみなしてよいような定義になっている
  - はその絶対値、はその標準化した値(0-1をとる)
    - 定義はこう！！！まちがっているかも知れない！！！ので要注意。定義から意訳してみている
  - - 上記で求めた $H$ について
    - $￥Large{￥Delta=1-￥frac{1}{H}}$
  - 定義
    - 半径が $R;R￥geq1$ であるようなグラフを想定する
    - それぞれのcenter i について要素数が最少であるノードの集合をとる。このはノード i のneighborsであるノードからなり、次の条件を満たす
      - $min￥{d(j,k):j￥in￥{i￥}￥cap{S_i}￥}￥leq{R-1}$ for all $k￥in G$
    - このようにして定義された $H_i$ のうち、最大のものを $H$ とする

Eccentricityが半径となっているようなノードをこのグラフの中心(center)と呼ぶ
非連結グラフ(Non-connected graph)の場合には、互いに非連結のグラフ上のノード間の距離を無限大と定義すると、上記のeccentricity,radius,diameterの定義はそのまま使用できる