計算機科学のブログ

グラフの基礎 有向グラフ 強連結グラフ 任意の2点、道

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第7章(グラフの基礎)、7.3(有向グラフ)、7.3.2(強連結グラフ)、問7.17の解答を求めてみる。

弱連結 、強連結である。
aからb、bからaへの道。

a c b b a

aから c 、 c から a への道。

a c c b a

aからd、 dからaへの 道。

a c d d a

bからc、 c からbへの道。

b a c c b

bからd、 dから b への道。

b a c d d a c b

cからd、 dから c への道。

c d d a c