出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
グラフ理論に関する説明として最も適切なものを選ぶ問題。単純閉路グラフの次数、完全2部グラフ、重み付きグラフ、ループと孤立点、無向完全グラフの辺の数を問う。
グラフ理論の基本用語(次数、完全グラフ、完全2部グラフ、孤立点など)を確認する問題。
① グラフの基本: 次数=頂点につながる辺の数。三角形の頂点はどれも2本。無向完全グラフの辺数は n(n−1)/2
② ②完全2部グラフは異なるグループ間だけつながる、③経路で重みは変わる、④ループがあれば孤立点ではない、⑤2nではない
③ ①
3つの頂点と3つの辺で構成される単純閉路グラフは、三角形の形になり、各頂点は、他の2つの頂点と1本ずつ辺で結ばれるため、いずれの頂点の次数も2である。したがって①が最も適切である。
次数=頂点に接続する辺の数(ループは2と数える)。無向完全グラフの辺数はn(n−1)/2。完全2部グラフでは、異なる集合の頂点間のみ、全て結ばれる。
キーワード: グラフ理論、次数、単純閉路、完全2部グラフ、無向完全グラフ、孤立点、辺の数、情報工学部門
同じ問題が計2回出題されています(平成28年度、令和元年度(再試験))。