単位距離グラフ

単位距離グラフの概要

単位距離グラフとは、ユークリッド平面上で全ての辺の長さが同じで、1の距離を持つ頂点同士を結ぶグラフです。このグラフでは、辺が交差しても構わず、平面グラフでなくなることもあります。特に平面グラフでもある単位距離グラフは「マッチ棒グラフ」と呼ばれています。

ハドヴィガー-ネルソン問題

単位距離グラフに関連する重要な問題に「ハドヴィガー-ネルソン問題」があります。この問題は、単位距離グラフの彩色数に関するもので、一部の単位距離グラフは5色で塗り分けられる一方で、少なくとも7色必要であることが分かっています。この問題は未解決の問いの一つであり、単位距離グラフの頂点の次数の上限がいくつであるかも検討されています。

単位距離グラフの例

様々なグラフが単位距離グラフの例として挙げられます。以下に代表的なものをリストします:

• - 閉路グラフ
• - 格子グラフ
• - 超立方体グラフ
• - スター
• - ペニーグラフ
• - ピーターセングラフ
• - ヒーウッドグラフ
• - 車輪グラフ W7
• - モーザースピンドル（4色で分ける必要がある、最小の単位距離グラフ）

単位距離グラフの直積は再び単位距離グラフになりますが、この性質は他の種類の積には当てはまりません。

単位距離グラフの部分グラフ

単位距離グラフでは、隣接していない頂点間においても、基本的には1の距離を持つものとして定義されることがあります。この観点から、メビウス-カントルグラフのように、隣接しない頂点間が単位距離で配置される場合もあります。これを「広義の単位距離グラフ」と呼び、一般化ピーターセングラフはこの範疇に入ります。狭義の単位距離グラフは、すべての隣接点が単位距離であることが求められるため、これを区別する必要があります。

単位距離の個数に関する問題

ポール・エルデシュは、n個の点がどれだけ密に単位距離のペアを持てるかを探究しました。エルデシュによって示された超立方体グラフは、O(n log n)の単位距離を持つとされており、他に正方形の格子状に配置して下限をO(n^{1+c/log log n})に改善しました。さらに、この問題の上限を設定することに500ドルの賞金がかけられています。最も良い上限は、O(n^{4/3})です。

代数的数の表現とベックマン-クォールズの定理

任意の代数的数Aに対して、その距離がAとなる単位距離グラフGが存在することが示されています。これは、点pとqの間の距離を保存する平面変換を通じて、規則的な単位距離グラフが持ち得る特性です。

高次元への一般化

単位距離グラフは高次元のユークリッド空間へも拡張可能です。必要な次元は、最大次数の2倍が上界とされる場合があります。全ての点間が単位距離で配置されるためには、必要とされる次元が異なることもあります。

計算複雑性

単位距離グラフが特定の形式であるかどうかを判定する問題は、計算上難しいとされており、更にハミルトン閉路が存在するかどうかもNP完全とされています。

参考文献

ここでは、単位距離グラフに関する参考文献を挙げています。数学界において広く引用されています。

もう一度検索