読者です 読者をやめる 読者になる 読者になる

強連結成分分解

有向グラフ上の部分集合Sの任意の頂点u, vについて,uからvに到達可能であるときSは強連結である。Sにどの頂点を加えても強連結にできないとき,Sは強連結成分である。

有向グラフGについて全ての強連結成分をつぶして一つにすると、グラフはDAGになる。

編集中