単位距離グラフのソースを表示

[[File:Petersen graph, unit distance.svg|thumb|upright|right|[[ピーターセングラフ]]は単位距離グラフの1つである。単位距離グラフは、すべての辺を単位長さにして平面に描画できる。]]

'''単位距離グラフ'''（たんいきょりグラフ、{{lang-en-short|unit distance graph}}）とは、[[グラフ理論]]のグラフの一種であり、[[ユークリッド平面]]上に、すべての辺の長さを単位長さとして描画できるグラフである。辺同士が交差してもよい（その場合[[平面グラフ]]ではなくなる）。平面グラフでもある単位距離グラフは、'''{{仮リンク|マッチ棒グラフ|en|matchstick graph}}'''と呼ばれる。

{{仮リンク|ハドヴィガー-ネルソン問題|en|Hadwiger–Nelson problem}}は、単位距離グラフの[[グラフ彩色|彩色数]]についての問題である。彩色数が5である単位距離グラフが存在する一方<ref>{{Cite news|url=http://www.sciencemag.org/news/2018/04/amateur-mathematician-cracks-decades-old-math-problem|title=Amateur mathematician cracks decades-old math problem|date=2018-04-18|work=Science {{!}} AAAS|access-date=2018-04-21|language=en}}</ref>、少なくとも7色で塗り分けられることが知られている。同様に重要な未解決問題に、単位距離グラフの頂点の[[次数_(グラフ理論)|次数]]の上限はいくつか？がある。

==例==
[[File:Hypercubestar.svg|thumb|150px|{{仮リンク|超立方体グラフ|en|hypercube graph}} ''Q''<sub>4</sub> は単位距離グラフである。]]
以下のグラフは、単位距離グラフである。
* [[閉路グラフ]]
* [[格子グラフ]]
* [[超立方体グラフ]]
* [[スター_(グラフ理論)|スター]]
* [[マッチ棒グラフ]]
* [[ペニーグラフ]]
* [[ピーターセングラフ]]
* [[ヒーウッドグラフ]] {{harv|Gerbracht|2009}}
* [[車輪グラフ]]の ''W''<sub>7</sub>
* [[モーザースピンドル]]（塗り分けに4色が必要な、最小の単位距離グラフ）

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

==単位距離グラフの部分グラフ==
[[File:Möbius–Kantor unit distance.svg|thumb|upright|left|{{仮リンク|メビウス-カントールグラフ|en|Möbius–Kantor graph}}の単位距離グラフ表現。]]辺で繋がっていない部分にも、単位距離だけ離れた頂点対が存在しうる。隣接する頂点対が単位距離だけ離れているように全ての頂点が平面内の別々の位置に配置され、隣接していない頂点対間の距離は単位距離であってもよいとしたグラフを単位距離グラフとして定義する場合もある。これを'''広義の単位距離グラフ'''と呼ぶ。例えばメビウス-カントルグラフはそのような頂点配置が可能な広義の単位距離グラフである。

この、広義の単位距離グラフの定義によれば、一般化[[ピーターセングラフ]]は全て単位距離グラフとなる{{harv|Žitnik|Horvat|Pisanski|2010}}。隣接していない頂点間の距離が単位距離であってはいけないという厳しい制約の単位距離グラフの定義は、緩い制約の定義と区別するために、'''狭義の単位距離グラフ'''と呼ぶこともある{{harv|Gervacio|Lim|Maehara|2008}}。

例えば、[[車輪グラフ]] ''W''<sub>7</sub> から1つの辺を除去したグラフは、単位距離グラフの部分グラフである。しかし、'''狭義の単位距離グラフ'''ではなくなる。車輪グラフの配置が、隣接する頂点が単位距離だけ離れているように頂点を配置する唯一の方法であり、除去された辺で隣接していた頂点対の距離は、単位距離となってしまう{{harv|Soifer|2008|p=94}}。

==単位距離の個数==
{{unsolved|数学|''n'' 点のグラフは、最大で何本の辺を持つ単位距離グラフを構成できるか？}}
[[File:Hamming33UnitDistance.gif|thumb|upright=1.3|[[ハミンググラフ]](3,3)]]

{{harvs|authorlink=Paul Erdős|last=Erdős|first=Paul|txt|year=1946}} は、 ''n'' 個の点を配置し、単位距離だけ離れた点対をいくつ生成できるか？という問題を考えた。グラフ理論的には、単位距離グラフをどこまで密にできるか？と言いかえられる。

[[超立方体グラフ]]は単位距離を<math>O(n\log n)</math>だけ有し、下界となる。正方形格子状に配置することで、ポール・エルデシュは下界を
:<math>O(n^{1+c/\log\log n}),</math>
まで改善した。
さらに、このような形式で上界を設けられるかという問題に対して500ドルの賞金を用意した{{harv|Kuperberg|1992}}。現在知られている最も良い上界は、{{harvs|txt|author1-link=Joel Spencer|last1=Spencer|first1=Joel|author2-link=Endre Szemerédi|last2=Szemerédi|first2=Endre|last3=Trotter|first3=William|year=1984}}による、:<math>O(n^{4/3})</math>
である。
この上界は単位円の隣接する個数としても考えられるため、[[Szemerédi–Trotter theorem]]と関連が深い。ハミンググラフ(3,3) はこの上界の1つであり、27頂点で81辺を持つ。

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

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

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

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

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

==参考文献==
{{Reflist}}
*{{citation
 | last1 = Beckman | first1 = F. S.
 | last2 = Quarles | first2 = D. A., Jr.
 | journal = Proceedings of the American Mathematical Society
 | mr = 0058193
 | pages = 810–815
 | title = On isometries of Euclidean spaces
 | volume = 4
 | year = 1953
 | doi=10.2307/2032415}}.
*{{citation
 | last = Erdős | first = Paul | author-link = Paul Erdős
 | doi = 10.2307/2305092
 | journal = [[American Mathematical Monthly]]
 | pages = 248–250
 | title = On sets of distances of ''n'' points
 | volume = 53
 | year = 1946
 | issue = 5
 | jstor = 2305092}}.
*{{citation
 | last1 = Erdős | first1 = Paul | author1-link = Paul Erdős
 | last2 = Simonovits | first2 = Miklós
 | journal = Ars Combinatoria
 | pages = 229–246
 | title = On the chromatic number of geometric graphs
 | volume = 9
 | year = 1980}}. As cited by {{harvtxt|Soifer|2008|p=97}}.
*{{citation
 | last = Gerbracht | first = Eberhard H.-A.
 | title = Eleven unit distance embeddings of the Heawood graph
 | year = 2009
 | arxiv = 0912.5395| bibcode = 2009arXiv0912.5395G}}.
*{{citation
 | last1 = Gervacio | first1 = Severino V.
 | last2 = Lim | first2 = Yvette F.
 | last3 = Maehara | first3 = Hiroshi
 | doi = 10.1016/j.disc.2007.04.050
 | issue = 10
 | journal = Discrete Mathematics
 | pages = 1973–1984
 | title = Planar unit-distance graphs having planar unit-distance complement
 | volume = 308
 | year = 2008}}.
*{{citation
 | last1 = Horvat | first1 = Boris
 | last2 = Pisanski | first2 = Tomaž | author2-link = Tomaž Pisanski
 | doi = 10.1016/j.disc.2009.11.035
 | issue = 12
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 2610282
 | pages = 1783–1792
 | title = Products of unit distance graphs
 | volume = 310
 | year = 2010}}.
*{{citation
 | last1 = Itai | first1 = Alon
 | last2 = Papadimitriou | first2 = Christos H. | author2-link = Christos Papadimitriou
 | last3 = Szwarcfiter | first3 = Jayme Luiz
 | doi = 10.1137/0211056
 | issue = 4
 | journal = [[SIAM Journal on Computing]]
 | mr = 677661
 | pages = 676–686
 | title = Hamilton paths in grid graphs
 | volume = 11
 | year = 1982}}.
*{{citation
 |last        = Kuperberg
 |first       = Greg
 |authorlink  = Greg Kuperberg
 |year        = 1992
 |title       = The Erdos kitty:  At least $9050 in prizes!
 |series      = Posting to usenet groups rec.puzzles and sci.math
 |url         = http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd
 |deadurl     = yes
 |archiveurl  = https://web.archive.org/web/20060929072712/http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd
 |archivedate = 2006-09-29
 |df          = 
}}.
*{{citation
  | journal = Discrete Applied Mathematics
  | volume = 31
  | issue = 2
  | year = 1991
  | pages = 193–200
  | doi = 10.1016/0166-218X(91)90070-D
  | title = Distances in a rigid unit-distance graph in the plane
  | last = Maehara | first = Hiroshi}}.
*{{citation
 | last = Maehara | first = Hiroshi
 | doi = 10.1016/0012-365X(92)90671-2
 | issue = 1-3
 | journal = Discrete Mathematics
 | mr = 1189840
 | pages = 167–174
 | title = Extending a flexible unit-bar framework to a rigid one
 | volume = 108
 | year = 1992}}.
*{{citation
  | last1 = Maehara | first1 = Hiroshi | last2 = Rödl | first2 = Vojtech
  | title = On the dimension to represent a graph by a unit distance graph
  | journal = [[Graphs and Combinatorics]]
  | volume = 6
  | issue = 4
  | year = 1990
  | pages = 365–367
  | doi = 10.1007/BF01787703}}.
*{{citation
 | last = Schaefer | first = Marcus
 | editor-last = Pach | editor-first = János | editor-link = János Pach
 | contribution = Realizability of graphs and linkages
 | doi = 10.1007/978-1-4614-0110-0_24
 | pages = 461–482
 | publisher = Springer
 | title = Thirty Essays on Geometric Graph Theory
 | year = 2013}}.
*{{citation
 | last = Soifer | first = Alexander | authorlink = Alexander Soifer
 | isbn = 978-0-387-74640-1
 | publisher = Springer-Verlag
 | title = The Mathematical Coloring Book
 | year = 2008}}.
*{{citation
  | author1-link=Joel Spencer|last1=Spencer|first1=Joel|author2-link=Endre Szemerédi|last2=Szemerédi|first2=Endre|last3=Trotter|first3=William T.
  | contribution = Unit distances in the Euclidean plane
  | title = Graph Theory and Combinatorics
  | publisher = Academic Press
  | year = 1984
  | pages = 293–308
  | location = London
  | isbn = 0-12-111760-X
  | mr = 0777185
  | editor1-first=Béla | editor1-last=Bollobás}}.
*{{citation
 | last = Tyszka | first = Apoloniusz
 | doi = 10.1007/PL00000119
 | issue = 1-2
 | journal = [[Aequationes Mathematicae]]
 | mr = 1741475
 | pages = 124–133
 | title = Discrete versions of the Beckman-Quarles theorem
 | volume = 59
 | year = 2000| arxiv = math/9904047
 }}.
*{{citation
 | last1 = Žitnik | first1 = Arjana
 | last2 = Horvat | first2 = Boris
 | last3 = Pisanski | first3 = Tomaž | author3-link = Tomaž Pisanski
 | series = IMFM preprints
 | title = All generalized Petersen graphs are unit-distance graphs
 | url = http://www.imfm.si/preprinti/PDF/01109.pdf
 | volume = 1109
 | year = 2010}}.

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

== 外部リンク ==
*{{citation
 |last       = Venkatasubramanian | first = Suresh
 |contribution = Problem 39: Distances among Point Sets in '''R'''<sup>2</sup> and '''R'''<sup>3</sup>
 |title        = The Open Problems Project
 |url          = http://cs.smith.edu/~jorourke/TOPP/P39.html}}
*{{mathworld|urlname=Unit-DistanceGraph|title=Unit-Distance Graph}}

{{Graph Theory-footer}}

{{デフォルトソート:たんいきよりくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]