グラフに関する用語

連結・関節点・橋・強連結・強連結成分

連結
任意の２点間に辺がある。 連結グラフは、グラフ上の任意の２点間に辺があるグラフのこと。

関節点
削除すると部分グラフが非連結になる点。

橋
削除すると部分グラフが非連結になる辺。

強連結
任意の2点間に有向路がある、という条件を満たしている有向グラフの頂点の部分集合を強連結であるという。

強連結成分
強連結な集合Sに、どのような頂点集合を付け足しても強連結にならないとき、Sを強連結成分という。