GraphDistanceMatrix

GraphDistanceMatrix[g]

グラフ g 内の頂点間の距離の行列を返す．

GraphDistanceMatrix[g,d]

グラフ g 内で最長距離を d とした頂点間の距離の行列を返す．

GraphDistanceMatrix[{vw,…},…]

規則 vw を使ってグラフ g を指定する．

詳細とオプション

  • GraphDistanceMatrixは最短経路行列としても知られている．
  • GraphDistanceMatrixはSparseArrayオブジェクトか通常の行列を返す．
  • 距離行列 dijの項目は頂点 viから頂点 vjまでの最短距離を与える．
  • 距離行列の対角項目 diiは常に0である．
  • 頂点 viから頂点 vjまでの経路が存在しない場合，項目 dijはInfinity(∞)である．
  • GraphDistanceMatrix[g,d]で頂点 viから頂点 vjまでに d ステップ以下の経路が存在しない場合，項目 dijはInfinityになる．
  • 頂点 viはVertexList[g]によって与えられる順序であるとみなされる．
  • 重み付きグラフについては，距離は頂点 viから頂点 vjまでの，任意の経路に沿った重みの和の最低のものである．
  • 使用可能なオプション
  • EdgeWeightAutomatic各辺の重み
    Method Automatic使用するメソッド
  • Methodの使用可能な設定値には，"Dijkstra"，"FloydWarshall"，"Johnson"がある．

例題

すべて開くすべて閉じる

例  (1)

ペテルセン(Petersen)グラフの距離行列を与える：

スコープ  (8)

GraphDistanceMatrixは無向グラフに使うことができる：

有向グラフ：

重み付きグラフ：

多重グラフ：

混合グラフ：

規則を使ってグラフを指定する：

それほど大きくないグラフの行列の列を1列抽出する：

GraphDistanceを使って同じ計算をするとより時間がかかる：

GraphDistanceMatrixは大きいグラフに使うことができる：

必要なのが1列のみのでグラフが大きい場合には，GraphDistanceを使った方が速い：

オプション  (6)

Method  (6)

メソッドは入力によって自動的に選ばれる：

"UnitWeight"メソッドはすべての辺に重み1を使う：

"Dijkstra"は辺の重みが正のグラフにのみ使うことができる：

"FloydWarshall"は負の辺の重みを含む有向グラフに使うことができる：

"Johnson"は負の辺の重みを含む有向グラフに使うことができる：

"Johnson"は疎なグラフでは"FloydWarshall"メソッドより速いことがある：

アプリケーション  (2)

グラフ全体を考慮して頂点離心率を求める：

強連結グラフの場合，結果はVertexEccentricityのものと一致する：

連結グラフのすべての頂点の頂点離心率を求める：

結果を検証する：

特性と関係  (5)

距離行列の行と列はVertexListで与えられた順に従う：

距離行列の対角項は常に0である：

GraphDistanceを使って距離行列を求めることができる：

連結グラフでは，頂点のVertexEccentricityは距離行列を使って計算できる：

別々の連結要素に属する2つの頂点間の距離はInfinityである：

考えられる問題  (2)

行列指標と頂点の間には想定される対応関係がないことがある：

2から3までの距離は予想される行列の位置にはない：

理由は頂点が予想される順序ではないからである：

Graph等の関数を呼ぶときに頂点を明示的に並べることで問題を解決する：

これで距離が予想される位置に求まるようになった：

"BellmanFord"は有効なMethodオプションではない：

代りに"FloydWarshall"，"Johnson"あるいはデフォルトで選択されるMethodを使う：

おもしろい例題  (1)

Wolfram Research (2010), GraphDistanceMatrix, Wolfram言語関数， https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html （2015年に更新）.

テキスト

Wolfram Research (2010), GraphDistanceMatrix, Wolfram言語関数， https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html （2015年に更新）.

CMS

Wolfram Language. 2010. "GraphDistanceMatrix." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html.

APA

Wolfram Language. (2010). GraphDistanceMatrix. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html

BibTeX

@misc{reference.wolfram_2024_graphdistancematrix, author="Wolfram Research", title="{GraphDistanceMatrix}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html}", note=[Accessed: 21-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_graphdistancematrix, organization={Wolfram Research}, title={GraphDistanceMatrix}, year={2015}, url={https://reference.wolfram.com/language/ref/GraphDistanceMatrix.html}, note=[Accessed: 21-November-2024 ]}