グラフ距離
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/09 02:06 UTC 版)
別の例としては、グラフ上の距離がある。グラフの2頂点P1、P2の間の距離は P1からP2へ到達するのに最低いくつの辺を通らねばならないかである。この特別な場合として離散群のケイリーグラフとその上の語距離 (word length metric) が挙げられる。これは離散群G上にその生成集合Sによって定まる距離で、Gの元 g, h の間の距離は g-1h を S の元の積として表すのに必要な項の数の最小数として定められる。有限生成群における、有限集合の範囲での生成集合の取り替えはケイリーグラフ上に互いに同値な距離を与える。
※この「グラフ距離」の解説は、「距離空間」の解説の一部です。
「グラフ距離」を含む「距離空間」の記事については、「距離空間」の概要を参照ください。
ウィキペディア小見出し辞書の「グラフ距離」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- グラフ距離のページへのリンク
