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