計算機科学のブログ

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

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

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

acbba

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

accba

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

acdda

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

baccb

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

bacddacb

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

cddac