グラフ理論に関する次の記述のうち,最も適切なものはどれか。
① 完全 2 部グラフは,すべての頂点同士が辺で繋がっている。
② 距離を重みとする重み付きグラフでは,ある頂点から別の頂点への移動に要する重みは,どの順路でも常に同じである。
③ 頂点から出た辺が同じ頂点に戻るループのみである場合,その頂点は孤立点である。
④ 3 つの頂点及び 3 つの辺で構成される単純閉路グラフならば,いずれの頂点でも次数は2である。
⑤ 無向完全グラフでは,頂点の数を n としたとき,辺の数は 2n となる。
答え
④
解説
① 完全 2 部グラフは,すべての頂点同士が辺で繋がっている。
完全 2 部グラフは同一の集合の頂点同士が繋がっている必要はないため,不適切です。
② 距離を重みとする重み付きグラフでは,ある頂点から別の頂点への移動に要する重みは,どの順路でも常に同じである。
順路によって重みが異なるため,不適切です。
③ 頂点から出た辺が同じ頂点に戻るループのみである場合,その頂点は孤立点である。
ループがあるということは,次数は 2 になるため,不適切です。
④ 3 つの頂点及び 3 つの辺で構成される単純閉路グラフならば,いずれの頂点でも次数は2である。
適切です。各頂点から他の 2 頂点に辺が引かれる三角形になります。
⑤ 無向完全グラフでは,頂点の数を n としたとき,辺の数は 2n となる。
辺の数は,1 / 2n(n-1) になります。