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

ウィキペディア小見出し辞書

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

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

「単位距離グラフ」の記事における「単位距離グラフの部分グラフ」の解説

辺で繋がっていない部分にも、単位距離だけ離れた頂点対が存在しうる。隣接する頂点対が単位距離だけ離れているように全ての頂点が平面内の別々の位置に配置され、隣接していない頂点対間の距離は単位距離であってもよいとしたグラフを単位距離グラフとして定義する場合もある。これを広義の単位距離グラフと呼ぶ。例えばメビウス-カントルグラフはそのような頂点配置が可能な広義の単位距離グラフである。 この、広義の単位距離グラフの定義によれば、一般化ピーターセングラフは全て単位距離グラフとなる(Žitnik, Horvat & Pisanski 2010)。隣接していない頂点間の距離が単位距離であってはいけないという厳しい制約の単位距離グラフの定義は、緩い制約の定義と区別するために、狭義の単位距離グラフと呼ぶこともある(Gervacio, Lim & Maehara 2008)。 The graph formed by removing one of the spokes from the 車輪グラフ W7 から1つの辺を除去したグラフは、単位距離グラフの部分グラフである。しかし、狭義の単位距離グラフではなくなる。車輪グラフの配置が、隣接する頂点が単位距離だけ離れているように頂点を配置する唯一の方法であり、除去された辺で隣接していた頂点対の距離は、単位距離となってしまう(Soifer 2008, p. 94)。