単位距離グラフ
良い記事ですね。詳しくはこちらをクリックしてください。

16頂点40辺の単位距離グラフ

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

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

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

意味

単位距離グラフとしてのピーターセングラフ[ 1 ]
単位距離グラフの部分グラフとしてのメビウス・カントールグラフ

平面上の点の集合に対する単位距離グラフは、それらの点を頂点とする無向グラフで、2つの頂点間のユークリッド距離がちょうど1であるときに、それらの頂点間に辺が1つ存在するものである。抽象グラフは、平面上で頂点の位置が異なり、辺の長さが単位となり、隣接していない頂点のペアの距離が単位にならない場合、単位距離グラフと呼ばれる。これが可能な場合、抽象グラフは、選ばれた位置の単位距離グラフと同型である。あるいは、より広い定義を用いて、隣接していない頂点のペアが単位距離であってもよいとする情報源もある。結果として得られるグラフは、単位距離グラフのサブグラフである（ここで定義）。[ 2 ]用語が曖昧な場合があるが、辺以外の距離が単位にならないグラフは、厳密な単位距離グラフ[ 3 ]または忠実な単位距離グラフと呼ばれることがある。[ 2 ]単位距離グラフの部分グラフは、平面上に1辺の長さだけを使って描くことができるグラフと同等である。[ 4 ]簡潔にするために、この記事ではこれらを「非厳密単位距離グラフ」と呼ぶ。

単位距離グラフは単位円グラフと混同してはならない。単位円グラフは距離が1以下の点のペアを結ぶグラフであり、無線通信ネットワークのモデル化によく使用される。[ 5 ]

例

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

超立方体グラフ は16の頂点と32の単位距離を持つ。質問4{\displaystyle Q_{4}}
ハミンググラフ は27の頂点と81の単位距離を持つH（3、3）{\displaystyle H(3,3)}

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

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

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

プロパティ

エッジの数

数学における未解決問題
点の集合によっていくつの単位距離を決定できますか?n{\displaystyle n}
数学におけるさらなる未解決問題

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

1959年、エルデシュとレオ・モーザーは、この問題の凸多角形の頂点に関する特殊なケースについて考察した。この場合、単位距離の最大数は である。[ 18 ]線形下限値 のみが知られている。[ 19 ]nログ2⁡n+4n{\displaystyle n\log _{2}n+4n}2n−7{\displaystyle 2n-7}

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

1、3、5、7、9、12、14、18、20、23、27、30、33、37、41、43、46、50、54、57（OEISの配列A186705）

禁制部分グラフ

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

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

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

代数的数と剛性

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

が1を法とする代数的数で単位根でないとき、 の冪の整数組み合わせは、単位距離グラフが無限次 を持つ複素数加法群の有限生成部分群を形成する。例えば、は多項式 の2つの複素根の1つとして選択することができ、4つの生成元を持つ無限次単位距離グラフを生成する。[ 26 ]α{\displaystyle \alpha}α{\displaystyle \alpha}α{\displaystyle \alpha}z4−z3−z2−z+1{\displaystyle z^{4}-z^{3}-z^{2}-z+1}

着色

数学における未解決問題
単位距離グラフの最大彩色数は何ですか?
数学におけるさらなる未解決問題

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

平面上のすべての点から形成される無限単位距離グラフの7色彩と、単位距離グラフとして埋め込まれた4色のモーザースピンドル

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

列挙

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

高次元への一般化

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

任意の有限グラフは、十分に高い次元で単位距離グラフとして埋め込むことができる。グラフによっては、非厳密な単位距離グラフとして埋め込む場合と厳密な単位距離グラフとして埋め込む場合で、非常に異なる次元が必要になる場合がある。例えば、-頂点クラウングラフは、非厳密な単位距離グラフ（つまり、すべての辺が単位長さになるグラフ）として4次元に埋め込むことができる。しかし、厳密な単位距離グラフとして埋め込むには、少なくとも次元が必要であり、その辺のみが単位距離のペアとなる。[ 32 ]任意のグラフを厳密な単位グラフとして実現するために必要な次元は、最大次数の2倍以下である。[ 33 ]2n{\displaystyle 2n}n−2{\displaystyle n-2}

計算の複雑さ

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

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

参考文献

注記

  1. ^グリフィス (2019) .
  2. ^ a b c dアロン＆クパフスキー（2014） .
  3. ^ a b c dジェルバシオ、リム、前原 (2008)。
  4. ^ a b Carmi et al. (2008) .
  5. ^ Huson & Sen (1995) .
  6. ^ a bチラカマリとマホニー (1995)。
  7. ^ a bエルデシュ、ハラリー、トゥッテ (1965)。
  8. ^ a b cホーヴァットとピサンスキー (2010)。
  9. ^ Brouwer & Haemers (2012) .
  10. ^エルデシュ、ハラリー、トゥッテ (1965) ;グリフィス (2019)
  11. ^ゲルブラハト (2009) .
  12. ^ Soifer (2008)、14–15、19 ページ。
  13. ^ジトニク、ホルヴァト、ピサンスキー (2012)。
  14. ^ a bラヴォレ＆スワンポール (2022)。
  15. ^ Szemerédi (2016) .
  16. ^エルデシュ (1990) .
  17. ^スペンサー、ゼメレディ、トロッター (1984) ;クラークソンら。 (1990) ;パッハとタルドス (2005) ;アゴストンとパルヴェルジ (2022)
  18. ^アガーワル (2015) .
  19. ^エーデルスブルナー＆ハイナル (1991)。
  20. ^アゴストンとパルヴェルジ (2022)。
  21. ^ a bグローバス＆パーシャル (2020)。
  22. ^ソイファー（2008）、94頁。
  23. ^前原（ 1991年、 1992年）。
  24. ^ Tyszka (2000) .
  25. ^ベックマン＆クォールズ（1953年）。
  26. ^ラドチェンコ (2021) .
  27. ^ランギン (2018) ;デ・グレイ (2018)
  28. ^ソイファー（2008）、17ページ。
  29. ^ワーマルド (1979) ;チラカマリ (1995) ;オドネル (1995)。
  30. ^クラークソンら（1990）。
  31. ^ Jaromczyk & Toussaint (1992) .
  32. ^エルデシュとシモノヴィッツ (1980)。
  33. ^前原・レードル（1990）。
  34. ^ a b Braß (2002) .
  35. ^ Matoušek (1993) ;時間における点と線の出現をリストするための密接に関連したアルゴリズムについては、 Chan & Zheng (2022)も参照してください。お（n4/3）{\displaystyle O(n^{4/3})}
  36. ^シェーファー (2013) .
  37. ^イタイ、パパディミトリウ、シュヴァルクフィター (1982)。

出典

「 https://en.wikipedia.org/w/index.php?title=Unit_distance_graph&oldid=1335608674」より取得