ノード1〜5をもつグラフを隣接行列で表したもののうち、木となるものはどれか。
ここで、隣接行列i 行j 列目の成分は、ノードi とノードj を結ぶエッジがある場合は1、ない場合は0とする。
| ア |  |
イ |  |
|
| ウ |  |
エ |  |
答え イ
【解説】
それぞれの隣接行列をグラフにすると
| ア |  |
イ |  |
|
| ウ |  |
エ |  |
【キーワード】
・隣接行列
- 隣接行列
グラフを表現するための行列で、n 個の頂点があるグラフを表現するときはn ×n の行列を作り、頂点a とb に枝(経路)があるときは、行列の第a 行第b 列と第b 行第a 列の要素が1になります。
もっと、「隣接行列」について調べてみよう。
戻る
一覧へ
次へ