距離（グラフ理論）

数学のグラフ理論の分野では、グラフ内の2つの頂点間の距離は、それらの頂点を結ぶ最短経路（グラフ測地線とも呼ばれる）の辺の数です。これは測地線距離または最短経路距離とも呼ばれます。^[1] 2つの頂点間には複数の最短経路が存在する場合があることに注意してください。^{[2] 2つの頂点を結ぶ}経路がない場合、つまり、それらが異なる連結成分に属する場合、通常、距離は無限大として定義されます。

有向グラフの場合、2つの頂点uとvの間の距離d ( u , v )は、 uからvへの弧からなる最短の有向パスの長さとして定義されます（そのようなパスが少なくとも1つ存在する場合）。^[3]無向グラフの場合とは対照的に、d ( u , v ) は必ずしもd ( v , u )と一致するとは限らないことに注意してください。つまり、これは単なる準距離であり、一方が定義されていてもう一方が定義されていない可能性があります。

点の集合に対して定義されたグラフ内の距離に基づいて定義された距離空間は、グラフ距離と呼ばれます。グラフが連結されている場合に限り、無向グラフの頂点集合と距離関数は距離空間を形成します。

頂点vの離心率 ϵ ( v )は、 vと他の頂点 間の最大距離である。記号で表すと、

${\displaystyle \epsilon (v)=\max _{u\in V}d(v,u).}$

これは、グラフ内でノードが最も遠いノードからどれだけ離れているかを表すものと考えることができます。

グラフの半径rは、任意の頂点の最小離心率、または記号で 表すと、

${\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u).}$

グラフの直径dは 、グラフ内の任意の頂点の最大離心率です。つまり、dは任意の2つの頂点間の最大距離、または、

${\displaystyle d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u).}$

グラフの直径を求めるには、まず各頂点のペア間の最短経路を求めます。これらの経路のうち最も長い経路がグラフの直径です。

半径rのグラフの中心の頂点は、離心率がrである頂点です。つまり、最も遠い頂点からの距離が半径に等しい頂点であり、ϵ ( v ) = rとなる頂点vです。

直径dのグラフにおける周辺頂点とは、離心率がdである頂点、つまり最も遠い頂点からの距離が直径に等しい頂点のことです。正式には、ϵ ( v ) = d のとき、 v は周辺頂点です。

擬似周辺頂点 v は、任意の頂点uについて、u がvから可能な限り離れている場合、v もuから可能な限り離れているという性質を持ちます。正式には、 d ( u , v ) = ϵ ( v )となる各頂点uについて、 ϵ ( u ) = ϵ ( v )が成り立つ場合、頂点 vは擬似周辺です。

グラフのレベル構造は、開始頂点が与えられた場合、グラフの頂点を開始頂点からの距離によってサブセットに 分割したものです。

測地グラフとは、頂点のペアごとに最短経路が一意に決まるグラフのことである。例えば、すべての木は測地グラフである。^[4]

重み付き最短経路距離は、測地線距離を重み付きグラフに一般化したものです。この場合、エッジの重みはその長さ、または複雑なネットワークの場合は相互作用のコストを表し、重み付き最短経路距離d ^W ( u , v )はuとvを接続するすべての経路の重みの最小合計であると想定されます。詳細とアルゴリズムについては、 最短経路問題を参照してください。

多くの場合、周辺スパース マトリックスアルゴリズムでは、離心率の高い開始頂点が必要になります。周辺頂点は最適ですが、計算が難しいことがよくあります。ほとんどの場合、疑似周辺頂点を使用できます。疑似周辺頂点は、次のアルゴリズムで簡単に見つけることができます。

1. 頂点を選択します。${\displaystyle u}$
2. から可能な限り遠いすべての頂点の中で、次数が最小の頂点を とします。${\displaystyle u}$${\displaystyle v}$
3. 設定した場合は手順 2 を繰り返し、そうでない場合は疑似周辺頂点になります。${\displaystyle \epsilon (v)>\epsilon (u)}$${\displaystyle u=v}$${\displaystyle u}$