単位距離グラフ

数学、特に幾何学的グラフ理論において、単位距離グラフは、ユークリッド平面上の点の集合から、それらの間の距離がちょうど 1 である 2 点を結ぶことによって形成されるグラフである。隣接していない頂点のペアが距離 1 にあることを許容するより広い定義と区別するために、これらのグラフは、厳密な単位距離グラフまたは忠実な単位距離グラフと呼ばれることもある。遺伝的グラフ族として、これらは禁制誘導サブグラフによって特徴付けられる。単位距離グラフには、サボテングラフ、マッチ棒グラフとペニーグラフ、およびハイパーキューブグラフが含まれる。一般化されたピーターセングラフは、厳密ではない単位距離グラフである。

ポール・エルデシュの未解決問題は、頂点上の単位距離グラフがいくつの辺を持つことができるかという問題である。最もよく知られている下限はでわずかに線形であり、上限からは遠く、 に比例する。単位距離グラフを着色するのに必要な色の数も不明である（ハドヴィガー・ネルソン問題）。単位距離グラフの中には 5 色を必要とするものもあり、すべての単位距離グラフは 7 色で着色できる。すべての代数的数に対して、その距離だけ離れた 2 つの頂点を持つ単位距離グラフが存在する。ベックマン・クォールズの定理によれば、すべての単位距離グラフを保存する平面変換は等長変換のみである。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle n^{4/3}}$

単位距離グラフは、その点が与えられれば効率的に構築できます。すべての単位距離を見つけることは、パターン マッチングに応用でき、より大きなパターンの合同なコピーを見つけるための最初のステップになります。ただし、与えられたグラフが単位距離グラフとして表現できるかどうかを判断することはNP 困難であり、より具体的には実数の存在理論では完全です。

平面上の点の集合に対する単位距離グラフは、それらの点を頂点とする無向グラフであり、 2つの頂点のユークリッド距離がちょうど1であるときは常に、2つの頂点の間に辺がある。抽象グラフは、その頂点に対して平面内で異なる位置を見つけることが可能であり、その辺の長さが単位であり、すべての隣接していない頂点のペアの距離が非単位である場合、単位距離グラフであると言われる。これが可能である場合、抽象グラフは、選択された位置の単位距離グラフと同型である。あるいは、一部の情報源では、より広い定義を使用して、隣接していない頂点のペアが単位距離にあることを許可している。結果として得られるグラフは、単位距離グラフのサブグラフである（ここで定義されているとおり）。 ^{[2]用語があいまいな場合、非辺が非単位距離離れている必要があるグラフは、}厳密な単位距離グラフ^[3]または忠実な単位距離グラフと呼ばれることがある。^[2]単位距離グラフのサブグラフは、1辺の長さのみを使用して平面に描画できるグラフと同等です。^[4]簡潔にするために、この記事ではこれらを「非厳密な単位距離グラフ」と呼びます。

単位距離グラフは、距離が1以下の点のペアを接続する単位ディスクグラフと混同しないでください。単位ディスクグラフは、無線通信ネットワークをモデル化するためによく使用されます。 ^[5]

2頂点の完全グラフは単位距離グラフであり、3頂点の完全グラフ（三角形グラフ）も同様であるが、4頂点の完全グラフはそうではない。^[3]三角形グラフを一般化すると、すべてのサイクルグラフは単位距離グラフであり、正多角形によって実現される。^[4] 2つの有限単位距離グラフを1つの共有頂点で接続すると、別の単位距離グラフが生成されます。これは、一方を他方に対して回転させて、不要な単位距離が追加されないようにできるためです。^[6]このようにグラフを接続すると、すべての有限木グラフまたはサボテングラフを単位距離グラフとして実現できます。^[7]

単位距離グラフの任意の直積は、別の単位距離グラフを生成しますが、他の一般的なグラフ積については同じことが当てはまりません。たとえば、グラフの強積を任意の 2 つの空でないグラフに適用すると、4 つの頂点を持つ完全なサブグラフが生成されますが、これは単位距離グラフではありません。パス グラフの直積は任意の次元のグリッド グラフを形成し、2 つの頂点を持つ完全グラフの直積はハイパーキューブ グラフ^[8]であり、三角形グラフの直積はハミンググラフ ^[9]です。${\displaystyle H(d,3)}$

単位距離グラフである他の特定のグラフには、ピーターセングラフ^[10]、 ヒーウッドグラフ^[11] 、 ホイールグラフ （単位距離グラフである唯一のホイールグラフ）^[3] 、モーザースピンドルおよびゴロムグラフ（小さな4彩色の単位距離グラフ） ^[12]などがあります。図示されているメビウス-カンターグラフなどの一般化されたピーターセングラフは すべて、非厳密な単位距離グラフです。^[13]${\displaystyle W_{7}}$

マッチ棒グラフは、単位距離グラフの特殊なケースで、辺が交差しません。すべてのマッチ棒グラフは平面グラフです^[14]が、それ以外は平面の単位距離グラフ (モーザースピンドルなど) の中には、単位距離グラフとして表現すると必ず交差するものがあります。また、単位距離グラフの文脈では、「平面」という用語は注意して使用する必要があります。著者の中には、交差の禁止ではなく、単位距離が定義されている平面を指すためにこの用語を使用している人もいます^[3] 。ペニーグラフは、単位距離グラフとマッチ棒グラフのさらに特殊なケースで、隣接していないすべての頂点のペアが 1 単位以上離れています^{[14] 。}

数学における未解決の問題:

点の集合によって決定できる単位距離はいくつですか?${\displaystyle n}$

（数学における未解決の問題がさらに増える）

ポール・エルデシュ(1946)は、点の集合の中で、互いに単位距離にある 点のペアが何組あるかを推定する問題を提起した。グラフ理論的に言えば、この問題は単位距離グラフがどれだけ密になり得るかを問うものであり、この問題に関するエルデシュの発表は極値グラフ理論における最初の研究の 1 つであった。^[15]ハイパーキューブグラフとハミンググラフは、 に比例する単位距離の数の下限値を提供する。慎重に間隔を選択した正方格子内の点を考慮することにより、エルデシュは、 定数 に対して の形式の下限値を改善し、単位距離の数もこの形式の関数によって上方に制限できるかどうかの証明に 500 ドルを提示した。^[16]この問題の最もよく知られている上限は、この上限は点と単位円の間の接続を数えることと見なすことができ、交差数不等式や点と線の間の接続に関するセメレディ・トロッターの定理と密接に関連している。^[17]${\displaystyle n}$${\displaystyle n\log n.}$$${\displaystyle n^{1+c/\log \log n}}$$${\displaystyle c}$$${\displaystyle {\sqrt[{3}]{\frac {29n^{4}}{4}}}\approx 1.936n^{4/3}.}$$

の値が小さい場合、可能なエッジの最大数は正確に分かっています。これらのエッジの数は次のとおりです: ^[18]${\displaystyle n}$${\displaystyle n=2,3,4,\dots }$

与えられたグラフが非厳密な単位距離グラフでない場合、のスーパーグラフも非厳密な単位距離グラフではありません。 同様の考え方が厳密な単位距離グラフにも適用できますが、誘導サブグラフ の概念を使用します。誘導サブグラフは、与えられた頂点のサブセット内の頂点のペア間のすべてのエッジから形成されるサブグラフです。 が厳密な単位距離グラフでない場合、 を誘導サブグラフとして持つ他のグラフも厳密な単位距離グラフではありません。 サブグラフまたはそのスーパーグラフが単位距離グラフであるかどうかの間にはこのような関係があるため、単位距離グラフをその禁制サブグラフによって記述することができます。これらは、与えられたタイプの単位距離グラフではない極小のグラフです。これらを使用して、与えられたグラフがどちらのタイプの単位距離グラフであるかを判定できます。が非厳密な単位距離グラフである場合、 は、非厳密な単位距離グラフの禁制グラフのスーパーグラフではありません。が厳密な単位距離グラフである場合、かつ、それが厳密な単位距離グラフの禁制グラフの誘導スーパーグラフではない場合に限ります。^[8]${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

非厳密な単位距離グラフと厳密な単位距離グラフの両方において、禁制グラフには完全グラフと完全二部グラフの両方が含まれます。 の場合、このグラフの2頂点側の頂点がどこに配置されていても、そこから単位距離内に他の3頂点を配置できる位置は最大でも2つしかないため、3つの頂点すべてを異なる点に配置することは不可能です。^{[8]これらは、最大5頂点の非厳密な単位距離グラフに対する禁制グラフの2つだけです。最大7頂点には6つの禁制グラフ[6]}があり、最大9頂点のグラフには74の禁制グラフがあります。 2つの単位距離グラフ（またはそのサブグラフ）を頂点で接着すると、厳密な（それぞれ非厳密な）単位距離グラフが生成されるため、すべての禁制グラフは2連結グラフであり、この接着プロセスでは形成できません。^[19]${\displaystyle K_{4}}$ ${\displaystyle K_{2,3}}$${\displaystyle K_{2,3}}$

ホイールグラフは 、6 つの頂点が単位正六角形を形成し、7 番目が六角形の中心にある、厳密な単位距離グラフとして実現できます。中心の頂点から 1 つの辺を削除すると、単位長さの辺を持つサブグラフが生成されますが、これは厳密な単位距離グラフではありません。頂点を正六角形に配置することは、隣接する頂点が単位距離離れるように頂点を別個の場所に配置する唯一の方法 (合同を除く) であり、この配置では、欠けている辺の 2 つの端点も単位距離に配置されます。したがって、これは厳密な単位距離グラフの禁制グラフですが、^[20]厳密でない単位距離グラフの 6 つの禁制グラフの 1 つではありません。厳密な単位距離グラフではないが非厳密な単位距離グラフであるグラフの他の例としては、から外辺を削除して形成されるグラフや、三角柱の三角形の1つから辺を削除して形成される6頂点グラフなどがある。^[19]${\displaystyle W_{7}}$ ${\displaystyle W_{7}}$

あらゆる代数的数 に対して、のすべての単位距離表現において、ある頂点のペアが の距離にあるような単位距離グラフを構成することが可能である。^[21]この結果は、ベックマン・クォールズの定理の有限バージョンを意味する。つまり、 とが互いに の距離にある場合、と を含む有限の剛体単位距離グラフが存在し、このグラフで単位距離を保存する平面の任意の変換によって、との間の距離も保存される。^[22]完全なベックマン・クォールズの定理は、単位距離を保存するユークリッド平面（または高次元ユークリッド空間）の変換は等長変換のみであることを述べている。同様に、平面内のすべての点によって生成される無限単位距離グラフでは、すべてのグラフ自己同型は、単位距離だけでなく、平面内のすべての距離を保存します。^[23]${\displaystyle \alpha}$${\displaystyle G}$${\displaystyle \alpha}$${\displaystyle G}$${\displaystyle p}$${\displaystyle q}$${\displaystyle \alpha}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p}$${\displaystyle q}$

が 1 を法とする代数的数で単位根でない場合、 のべき乗の整数結合は、単位距離グラフが無限次 を持つ複素数の加法群の有限生成部分群を形成します。たとえば、 は多項式 の 2 つの複素根の 1 つとして選択でき、4 つの生成元を持つ無限次単位距離グラフを生成します。^[24]${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle z^{4}-z^{3}-z^{2}-z+1}$

ハドヴィガー・ネルソン問題は、単位距離グラフの彩色数、より具体的にはユークリッド平面のすべての点から形成される無限単位距離グラフの彩色数に関する問題である。選択公理を仮定するド・ブリュイン・エルデシュの定理によれば、これは有限単位距離グラフの最大彩色数を求めることと同等である。任意の適切な彩色で5色を必要とする単位距離グラフが存在し、^[25]すべての単位距離グラフは最大で7色で彩色することができる。^[26]

ポール・エルデシュの別の質問に答えると、三角形のない単位距離グラフには4色が必要になる可能性がある。 ^[27]

ラベル付き頂点上の厳密な単位距離グラフの数は、大O表記と小O表記 を使用して表すと最大^[2]です。 ${\displaystyle n\geq 4}$ $${\displaystyle {\binom {n(n-1)}{2n}}=O\left(2^{{\bigl (}4+o(1){\bigr )}n\log _{2}n}\right),}$$

単位距離グラフの定義は、当然、任意の高次元ユークリッド空間に一般化できます。3次元では、点の単位距離グラフには最大で 個の辺があり、 は逆アッカーマン関数に関連する非常にゆっくりと増加する関数です。^{[28]この結果から、3次元}相対近傍グラフの辺の数についても同様の制限が導かれます。^[29] 4次元以上では、任意の完全二部グラフは単位距離グラフであり、共通の中心を持つ2つの垂直な円上に点を配置することで実現されるため、単位距離グラフは稠密グラフになることができます。^[7]単位距離グラフの列挙式は高次元に一般化され、4次元以上では厳密な単位距離グラフの数が単位距離グラフのサブグラフの数よりもはるかに多いことを示しています。^[2]${\displaystyle n}$${\displaystyle n^{3/2}\beta (n)}$${\displaystyle \beta}$

任意の有限グラフは、十分に高い次元で単位距離グラフとして埋め込むことができる。一部のグラフでは、非厳密な単位距離グラフと厳密な単位距離グラフとして埋め込むために、非常に異なる次元が必要になることがある。たとえば、-頂点クラウングラフは、非厳密な単位距離グラフとして 4 次元に埋め込むことができる (つまり、すべての辺の長さが単位になる)。ただし、厳密な単位距離グラフとして埋め込むには、少なくとも次元が必要であり、その辺だけが単位距離のペアになる。^[30]任意のグラフを厳密な単位グラフとして実現するために必要な次元は、最大次数の 2 倍以下である。^[31]${\displaystyle 2n}$${\displaystyle n-2}$

点から単位距離グラフを構築することは、より大きな点集合からあるパターンの合同なコピーを見つけるための他のアルゴリズムにとって重要なステップである。これらのアルゴリズムは、この構築を使用して、パターン内の距離の1つが存在する候補位置を検索し、次に他の方法を使用して各候補のパターンの残りの部分をテストする。^[32]この問題には、Matoušek (1993) の方法を適用することができ、^{[32] は、}ゆっくりと増加する反復対数関数である、時間内に平面点集合の単位距離グラフを見つけるアルゴリズムを生み出す。^[33]${\displaystyle n^{4/3}2^{O(\log^{*}n)}}$${\displaystyle \log^{*}}$

与えられたグラフが平面上の（厳密または非厳密な）単位距離グラフであるかどうかをテストすることはNP困難であり、より具体的には、実数体の存在理論にとって完全である。 ^{[34]平面単位距離グラフに}ハミルトン閉路があるかどうかを判断することも、グラフの頂点がすべて既知の整数座標を持つ場合でもNP完全である。 ^[35]

• Venkatasubramanian, Suresh、「問題 39: R2 と R3 の点集合間の距離」、The Open Problems Project
• ワイスシュタイン、エリック W.、「単位距離グラフ」、MathWorld