単位距離グラフ

ウィキペディア

単位距離グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/01/15 00:24 UTC 版)

ピーターセングラフは単位距離グラフの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)}$ カテゴリ / コモンズ