技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。

�@　無向グラフにおいて閉路がないとき、そのグラフが必ず木であるとは限らない。

�A　有向グラフが連結であるとき、その各辺の向きを無視することで得られ無向グラフは無向グラフとして連結である。

�B　グラフが疎 (sparse) であるとは、頂点数が n のときに辺の数がO(n) 程度であることである。

�C　ネットワークとは、グラフの各辺に数値が付与されているものである。

�D　有向グラフを隣接行列によって表現するとき、頂点数をnとすると、表現のために必要なメモリ量はO(n²) である。

�@　間違っている記述である。無向グラフにおいて閉路がないとき、そのグラフは必ず木となる。

�A　有向グラフは矢印付きの辺と考えるとよい。矢印がついた辺が連結していると、矢印を無視しても連結である。

�B　O(n) は計算量である。

�C　正しい記述である。

�D　隣接行列は、頂点と頂点を結ぶ辺 (枝) の数を行列形式で表したものである。例えば頂点が4個なら、4×4の行列で表現する。