単位距離グラフ

単位距離グラフ（たんいきょりグラフ、）とは、グラフ理論のグラフの一種であり、ユークリッド平面上に、すべての辺の長さを単位長さとして描画できるグラフである。辺同士が交差してもよい（その場合平面グラフではなくなる）。平面グラフでもある単位距離グラフは、と呼ばれる。

は、単位距離グラフの彩色数についての問題である。彩色数が5である単位距離グラフが存在する一方、少なくとも7色で塗り分けられることが知られている。同様に重要な未解決問題に、単位距離グラフの頂点の次数の上限はいくつか？がある。

例
以下のグラフは、単位距離グラフである。
 閉路グラフ
 格子グラフ
 超立方体グラフ
 スター
 マッチ棒グラフ
 ペニーグラフ
 ピーターセングラフ
 ヒーウッドグラフ 
 車輪グラフの W7
 モーザースピンドル（塗り分けに4色が必要な、最小の単位距離グラフ）

単位距離グラフの直積は、また別の単位距離グラフとなる。しかし、他の積についても成り立つわけではない。

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

この、広義の単位距離グラフの定義によれば、一般化ピーターセングラフは全て単位距離グラフとなる。隣接していない頂点間の距離が単位距離であってはいけないという厳しい制約の単位距離グラフの定義は、緩い制約の定義と区別するために、狭義の単位距離グラフと呼ぶこともある。

例えば、車輪グラフ W7 から1つの辺を除去したグラフは、単位距離グラフの部分グラフである。しかし、狭義の単位距離グラフではなくなる。車輪グラフの配置が、隣接する頂点が単位距離だけ離れているように頂点を配置する唯一の方法であり、除去された辺で隣接していた頂点対の距離は、単位距離となってしまう。

単位距離の個数


 は、 n 個の点を配置し、単位距離だけ離れた点対をいくつ生成できるか？という問題を考えた。グラフ理論的には、単位距離グラフをどこまで密にできるか？と言いかえられる。

超立方体グラフは単位距離をだけ有し、下界となる。正方形格子状に配置することで、ポール・エルデシュは下界を

まで改善した。
さらに、このような形式で上界を設けられるかという問題に対して500ドルの賞金を用意した。現在知られている最も良い上界は、による、:
である。
この上界は単位円の隣接する個数としても考えられるため、Szemerédi–Trotter theoremと関連が深い。ハミンググラフ(3,3) はこの上界の1つであり、27頂点で81辺を持つ。

代数的数の表現とベックマン-クォールズの定理
任意の代数的数 A に対し、頂点間の距離が A となるような単位距離グラフ G が存在する。これはベックマン-クォールズの定理の有限な場合に対応し、 A だけ離れた任意の2点 p と qに対し、単位距離を保存する平面変換が p と q の間の距離を保存するような p と q を含む有限のrigidな単位距離グラフが存在することを示している。ベックマン-クォールズの定理は、ユークリッド空間に対する任意の変換が、単位距離を保存する場合、等長であることを良い、任意の場所を頂点とするような無限単位距離グラフに対して、グラフが自己同型ならば等長であることに対応する。

高次元への一般化
単位距離グラフは、高次元ユークリッド空間に拡張できる。グラフは、十分に高い次元の点の集合として考えられる。前原は、グラフを高次元に埋め込む際、必要な次元は、最大次数の2倍が上界となる可能性があることを示した。

すべての点間が単位距離となるために必要な次元と、辺が単位距離になるために必要な次元は、大きく異なる場合がある。例えば、2n -頂点のcrown graphは、4次元ですべての辺が単位長さになるような配置を有するが、全ての点間が単位距離となるためには少なくとも n - 2次元が必要である。

計算複雑性
与えられたグラフが単位距離グラフであるか狭義の単位距離グラフであるかを判定する問題はNP困難である。

単位距離グラフがハミルトン閉路を持つかどうかは、グラフの頂点がすべて整数座標を持つ場合でもNP完全である。

参考文献

.
.
. As cited by .
.
.
.
.
.
.
.
.
.
.
.
.
.

関連項目
単位円グラフ　2頂点間の距離が単位長さ以下である場合に辺を持つグラフ

 外部リンク 

Category:グラフ理論のグラフ
Category:数学に関する記事