午前問6
ノード1〜5をもつグラフを隣接行列で表したもののうち、木となるものはどれか。ここで、隣接行列のi行j列目の成分は、ノードiとノードjを結ぶエッジがある場合は1、ない場合は0とする。
 | |
 | |
 |
『情報処理過去問.com』からiPhoneアプリがリリースされました！！
正解
- イ
解説
| ア. | |
| ノード間のエッジは「1－2」「1－5」「2－3」「3－4」「4－5」で全てループ構造になっているので木ではありません。 | |
| イ. | |
| ノード間のエッジは「1－2」「1－5」「2－3」「2－3」で「2」を根とした木となっているので正解です。 | |
| ウ. | |
| ノード間のエッジは「1－2」「1－4」「2－3」「3－4」「3－5」で「1〜4」がループ構造になっているので木ではありません。 | |
| エ. | |
| ノード間のエッジは「1－2」「1－3」「2－3」「3－4」「3－5」「4－5」で「1〜3」「3〜5」がループ構造になっているので木ではありません。 |