グラフ

質問

掲載した画像のグラフについてです。

このとき、隣接行列は、
|00000|
|00010|
|10000|
|00100|
|00000|
↑５行５列のことです。

また、可到達行列は、
|00000|
|10110|
|01010|
|10100|
|10110|
↑５行５列のことです。

でいいんでしょうか？

また、強連結成分は、{2,3,4}でしょうか？

回答No.3

Tacosan

隣接行列はそれで OK. 可到達行列はすべての対角成分が 1 になりませんか?
強連結成分は定義をきちんと理解しておかないと分かりづらいんだけど
{1}, {2, 3, 4}, {5}
の 3つです. {1} とか {5} が強連結成分であることに気づかない可能性が高い.

回答No.2

Tacosan

つまり, 隣接行列の全ての成分を加えると辺の本数になるはずですよね. そう考えたら, その「隣接行列」が間違っていることはほぼ一瞬でわかるはずです. 可到達行列でも, 例えば 2→5 は到達可能だから (2, 5) 成分は 1 になるはずです.
強連結成分は... まあ, 定義がわからんとわからんかも.

補足

隣接行列は、
|00000|
|00010|
|11000|
|00101|
|00000|

可到達行列は、
|00000|
|10111|
|11011|
|11101|
|00000|
ですか？

強連結成分は、任意の x, y に対して有向道 x --> y が存在することですよね。だったら、{2,4,3,1}、{3,2,4,5}、{3,2,4}でしょうか？お願いです。Tacosanさん、正解を教えてください。ヒントでもいいです。

回答No.1

Tacosan

隣接行列や可到達行列の定義は理解できてますか? 書いてみてください.
{2, 3, 4} は強連結成分の 1つですが, 他にもあります.

補足

隣接行列は、ある頂点 v と w の間の枝の本数を行列の (v, w) 成分に割り当てるグラフ、可到達行列は、直接、間接の因果関係のすべてをあらわす行列です。強連結成分については、イマイチわかっていません・・・すいません。