9.强连通图和强连通分量 在有向图G中若从页点v到顶点v 有路径则称从v到v是连通的。 若图G中的任意两个顶点v和v都 连通,即从v到v和从v到v都存在路径, 则称图G是强连通图。例如右边两个 图都是强连通图。 有向图G中的极大强连通子图称为 G的强连通分量。显然强连通图只有 一个强连通分量,即本身非强连通图有 (b) 多个强连通分量。9. 强连通图和强连通分量 在有向图G中,若从顶点vi到顶点vj 有路径,则称从vi到vj是连通的。 若图G中的任意两个顶点vi和vj都 连通,即从vi到vj和从vj到vi都存在路径, 则称图G是强连通图。例如,右边两个 图都是强连通图。 有向图G中的极大强连通子图称为 G的强连通分量。显然,强连通图只有 一个强连通分量,即本身,非强连通图有 多个强连通分量。 1 2 0 3 （a） 1 2 0 （b）