平成16年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
W−3
データ構造としてのグラフに関する次の記述に対して、間違っているものを選べ。
グラフの多重辺、自己辺はないものとする。

 @ 無向グラフにおいて閉路がないとき、そのグラフが必ず木であるとは
   限らない。
 A 有向グラフが連結であるとき、その各辺の向きを無視することで得られ
   無向グラフは無向グラフとして連結である。
 B グラフが疎 (sparse) であるとは、頂点数が n のときに辺の数が(n)
   程度であることである。
 C ネットワークとは、グラフの各辺に数値が付与されているものである。
 D 有向グラフを隣接行列によって表現するとき、頂点数をnとすると、
   表現のために必要なメモリ量は(n2) である。



【正解】 @

@無向グラフにおいて閉路がないとき、そのグラフは必ず木となる。
A有向グラフは矢印付きの辺と考えるとよい。
 矢印がついた辺が連結していると、矢印を無視しても連結である。
B(n) は計算量である。
D隣接行列は、頂点と頂点を結ぶ辺 (枝) の数を行列形式で表したもので
 ある。
 例えば頂点が4個なら、 4×4の行列で表現する。


EXCELのマクロのご相談なら ファーストマクロ 



W−2 目次 W−4
ファーストマクロ TOPページ