単位距離グラフ

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

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

例

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

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

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

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

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

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

単位距離の個数

数学の未解決問題
n 点のグラフは、最大で何本の辺を持つ単位距離グラフを構成できるか？

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

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

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

まで改善した。さらに、このような形式で上界を設けられるかという問題に対して500ドルの賞金を用意した(Kuperberg 1992)。現在知られている最も良い上界は、Joel Spencer, Endre Szemerédi, and William Trotter (1984)による、: $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)。

参考文献

^ “Amateur mathematician cracks decades-old math problem” (英語). Science | AAAS. (2018年4月18日) 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, MR 0058193 .
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時点におけるアーカイブ。 .
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 .

外部リンク

Venkatasubramanian, Suresh, “Problem 39: Distances among Point Sets in R² and R³”, The Open Problems Project
Weisstein, Eric W. "Unit-Distance Graph". mathworld.wolfram.com (英語).

[1] “Amateur mathematician cracks decades-old math problem” (英語). Science | AAAS. (2018年4月18日) 2018年4月21日閲覧。

[1]

表話編歴グラフ理論
要素・定義・表現	頂点辺（英語版）グラフ無向有向ラベル付き（英語版）重み付き（英語版）ハイパーグラフ接続行列隣接行列隣接リスト
指標	位数（英語版）サイズ（英語版）次数次数行列距離（英語版）半径直径内周 (頂点)彩色数辺彩色数（英語版）点連結度辺連結度交叉数（英語版）
部分構造	ループ（英語版）多重辺（英語版）部分グラフ（英語版）誘導部分グラフ道閉道連結成分（英語版）強連結成分（英語版）橋（英語版）カットクリーク独立集合支配集合（英語版）マッチングオイラー路シュタイナー木全域木ハミルトン路
全体構造	連結グラフ正則グラフ立方体グラフケージ強正則グラフ木平面グラフ 2部グラフ有向非巡回グラフ弦グラフムーアグラフパーフェクトグラフ対称グラフ半対称グラフ頂点推移グラフ辺推移グラフ距離推移グラフ補グラフ双対グラフグラフ同型
固有名を持つグラフ	パスグラフ（英語版） $P n$ 閉路グラフ $C n$ 完全グラフ $K n$ 完全2部グラフ $K m, n$ スター $S n = K 1, n$ 車輪グラフ $W n$ 空グラフピーターセングラフヒーウッドグラフマギーグラフホフマンシングルトングラフフォークマングラフ
トピック・定理	一筆書きオイラーの多面体定理クラトフスキの定理四色定理五色定理ケイリーの公式プリューファー列最短経路問題巡回セールスマン問題中国人郵便配達問題ダイクストラ法ベルマン-フォード法ワーシャル-フロイド法ハミルトン閉路問題最大クリーク問題頂点被覆問題最小頂点被覆問題最大独立集合問題最大流最小カット定理支配集合問題次数直径問題安定結婚問題
カテゴリ / コモンズ

例