4-3 グラフマスターへの道

強連結成分分解

• 強連結: 任意の 2 頂点 $u,v$ について $u$ から $v$ へのパスが存在するような状態
• 強連結成分, SCC(Strong Connected Component): 強連結な頂点集合に，他のどの頂点集合を付け加えても強連結にできない

どんな有向グラフもいくつかの強連結成分に分解することができ，強連結成分を一つの頂点と考えると，元のグラフはDAGになる．