高次元への一般化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:50 UTC 版)
単位距離グラフは、高次元ユークリッド空間に拡張できる。グラフは、十分に高い次元の点の集合として考えられる。前原は、グラフを高次元に埋め込む際、必要な次元は、最大次数の2倍が上界となる可能性があることを示した。 すべての点間が単位距離となるために必要な次元と、辺が単位距離になるために必要な次元は、大きく異なる場合がある。例えば、2n -頂点のcrown graphは、4次元ですべての辺が単位長さになるような配置を有するが、全ての点間が単位距離となるためには少なくとも n - 2次元が必要である(Erdős & Simonovits 1980)。
※この「高次元への一般化」の解説は、「単位距離グラフ」の解説の一部です。
「高次元への一般化」を含む「単位距離グラフ」の記事については、「単位距離グラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「高次元への一般化」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 高次元への一般化のページへのリンク
