単位距離グラフ

ピーターセングラフは単位距離グラフの1つである。単位距離グラフは、すべての辺を単位長さにして平面に描画できる。

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

ハドヴィガー-ネルソン問題（英語版）は、単位距離グラフの彩色数についての問題である。彩色数が5である単位距離グラフが存在する一方^[1]、少なくとも7色で塗り分けられることが知られている。同様に重要な未解決問題に、単位距離グラフの頂点の次数の上限はいくつか？がある。

例

超立方体グラフ（英語版） Q₄ は単位距離グラフである。

以下のグラフは、単位距離グラフである。

• 閉路グラフ
• 格子グラフ
• 超立方体グラフ
• スター
• マッチ棒グラフ
• ペニーグラフ
• ピーターセングラフ
• ヒーウッドグラフ (Gerbracht 2009)
• 車輪グラフの W₇
• モーザースピンドル（塗り分けに4色が必要な、最小の単位距離グラフ）

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

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

メビウス-カントールグラフ（英語版）の単位距離グラフ表現。

辺で繋がっていない部分にも、単位距離だけ離れた頂点対が存在しうる。隣接する頂点対が単位距離だけ離れているように全ての頂点が平面内の別々の位置に配置され、隣接していない頂点対間の距離は単位距離であってもよいとしたグラフを単位距離グラフとして定義する場合もある。これを広義の単位距離グラフと呼ぶ。例えばメビウス-カントルグラフはそのような頂点配置が可能な広義の単位距離グラフである。

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

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

単位距離の個数

数学の未解決問題

n 点のグラフは、最大で何本の辺を持つ単位距離グラフを構成できるか？

ハミンググラフ(3,3)

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

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

${\displaystyle O(n^{1+c/\log \log n}),}$

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

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

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

高次元への一般化

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

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

計算複雑性

与えられたグラフが単位距離グラフであるか狭義の単位距離グラフであるかを判定する問題はNP困難である(Schaefer 2013)。

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

参考文献

1. “Amateur mathematician cracks decades-old math problem” (英語). Science | AAAS. (2018年4月18日). http://www.sciencemag.org/news/2018/04/amateur-mathematician-cracks-decades-old-math-problem 2018年4月21日閲覧。 

• Beckman, F. S.; Quarles, D. A., Jr. (1953), “On isometries of Euclidean spaces”, Proceedings of the American Mathematical Society 4: 810–815, doi:10.2307/2032415, MR0058193 .
• Erdős, Paul (1946), “On sets of distances of n points”, American Mathematical Monthly 53 (5): 248–250, doi:10.2307/2305092, JSTOR 2305092, https://jstor.org/stable/2305092 .
• Erdős, Paul; Simonovits, Miklós (1980), “On the chromatic number of geometric graphs”, Ars Combinatoria 9: 229–246 . As cited by Soifer (2008, p. 97).
• Gerbracht, Eberhard H.-A. (2009), Eleven unit distance embeddings of the Heawood graph, arXiv:0912.5395, Bibcode: 2009arXiv0912.5395G .
• Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008), “Planar unit-distance graphs having planar unit-distance complement”, Discrete Mathematics 308 (10): 1973–1984, doi:10.1016/j.disc.2007.04.050 .
• Horvat, Boris; Pisanski, Tomaž (2010), “Products of unit distance graphs”, Discrete Mathematics 310 (12): 1783–1792, doi:10.1016/j.disc.2009.11.035, MR2610282 .
• Itai, Alon; Papadimitriou, Christos H.; Szwarcfiter, Jayme Luiz (1982), “Hamilton paths in grid graphs”, SIAM Journal on Computing 11 (4): 676–686, doi:10.1137/0211056, MR677661 .
• Kuperberg, Greg (1992), The Erdos kitty: At least $9050 in prizes!, Posting to usenet groups rec.puzzles and sci.math, オリジナルの2006-09-29時点におけるアーカイブ。, https://web.archive.org/web/20060929072712/http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd .
• Maehara, Hiroshi (1991), “Distances in a rigid unit-distance graph in the plane”, Discrete Applied Mathematics 31 (2): 193–200, doi:10.1016/0166-218X(91)90070-D .
• Maehara, Hiroshi (1992), “Extending a flexible unit-bar framework to a rigid one”, Discrete Mathematics 108 (1-3): 167–174, doi:10.1016/0012-365X(92)90671-2, MR1189840 .
• Maehara, Hiroshi; Rödl, Vojtech (1990), “On the dimension to represent a graph by a unit distance graph”, Graphs and Combinatorics 6 (4): 365–367, doi:10.1007/BF01787703 .
• Schaefer, Marcus (2013), “Realizability of graphs and linkages”, in Pach, János, Thirty Essays on Geometric Graph Theory, Springer, pp. 461–482, doi:10.1007/978-1-4614-0110-0_24 .
• Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, ISBN 978-0-387-74640-1 .
• Spencer, Joel; Szemerédi, Endre; Trotter, William T. (1984), “Unit distances in the Euclidean plane”, in Bollobás, Béla, Graph Theory and Combinatorics, London: Academic Press, pp. 293–308, ISBN 0-12-111760-X, MR0777185 .
• Tyszka, Apoloniusz (2000), “Discrete versions of the Beckman-Quarles theorem”, Aequationes Mathematicae 59 (1-2): 124–133, arXiv:math/9904047, doi:10.1007/PL00000119, MR1741475 .
• Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), All generalized Petersen graphs are unit-distance graphs, IMFM preprints, 1109, http://www.imfm.si/preprinti/PDF/01109.pdf .

関連項目

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

外部リンク

• Venkatasubramanian, Suresh, “Problem 39: Distances among Point Sets in R² and R³”, The Open Problems Project, http://cs.smith.edu/~jorourke/TOPP/P39.html 
• Weisstein, Eric W. "Unit-Distance Graph". mathworld.wolfram.com (英語).