演習4-6

右の図1で示したネットワークに関して，次の問に答えよ．

図1：有向グラフ
（1）
 図1で示したネットワークの基になる有向グラフを隣接行列，接続行列，リスト表現で各々示せ．（グラフ構造のみを表現すればよく，各枝に付されたデータを表現する必要はない．）
（2） 点v1を根として幅優先探索を行ったときの探索木を図示せよ．
（3） 点v1を根として奥優先探索を行ったときの探索木を図示せよ．
（4） 上記（3）での探索に対し，各点に先行順（前順）で番号付けをせよ．
（5）
 上記（3）での探索に対し，各点に後行順（後順）で番号付けをせよ．
（6）
 図1で示したネットワークの基になる有向グラフを強連結成分分解し，その構造をHasse図で示せ．
2001年度 OR期末試験 問題1（改題）
作成： 根本 俊男(文教大学情報学部経営情報学科)
　 e-mail: nemoto@shonan.bunkyo.ac.jp