技術士試験ナビ

技術士試験対策・テキスト・過去問題解説を発信します。

技術士第一次試験専門科目 平成28年度 Ⅲ-6

 グラフ理論に関する次の記述のうち,最も適切なものはどれか。

① 完全 2 部グラフは,すべての頂点同士が辺で繋がっている。

② 距離を重みとする重み付きグラフでは,ある頂点から別の頂点への移動に要する重みは,どの順路でも常に同じである。

③ 頂点から出た辺が同じ頂点に戻るループのみである場合,その頂点は孤立点である。

④ 3 つの頂点及び 3 つの辺で構成される単純閉路グラフならば,いずれの頂点でも次数は2である。

⑤ 無向完全グラフでは,頂点の数を n としたとき,辺の数は 2n となる。

 

 

答え

      ④

解説

① 完全 2 部グラフは,すべての頂点同士が辺で繋がっている。
完全 2 部グラフは同一の集合の頂点同士が繋がっている必要はないため,不適切です。

② 距離を重みとする重み付きグラフでは,ある頂点から別の頂点への移動に要する重みは,どの順路でも常に同じである。
順路によって重みが異なるため,不適切です。

③ 頂点から出た辺が同じ頂点に戻るループのみである場合,その頂点は孤立点である。
ループがあるということは,次数は 2 になるため,不適切です。

④ 3 つの頂点及び 3 つの辺で構成される単純閉路グラフならば,いずれの頂点でも次数は2である。
適切です。各頂点から他の 2 頂点に辺が引かれる三角形になります。

⑤ 無向完全グラフでは,頂点の数を n としたとき,辺の数は 2n となる。
辺の数は,1 / 2n(n-1) になります。