强连通图与强连通分量在有向图中,若对于每一对顶 点v和v都存在一条从w到v和从v到v的路径,则称此 是强连通图。非强连通图的极大强连通子图叫做强 连通分量。 生成树一个连通图的生成树是它的极小连通子图, 在n个顶点的情那下,有n-1条边 令生成树是对指连通图来而言的 令是连同图的极小连同子图 令包含图中的所有顶点 令有且仅有n-条边 本章不予 讨论的图 d a)带自身环的图 b)多重图强连通图与强连通分量 在有向图中, 若对于每一对顶 点vi和vj , 都存在一条从vi到vj和从vj到vi的路径, 则称此 图是强连通图。非强连通图的极大强连通子图叫做强 连通分量。 生成树 一个连通图的生成树是它的极小连通子图， 在n个顶点的情形下，有n-1条边。 ❖ 生成树是对指连通图来而言的 ❖ 是连同图的极小连同子图 ❖ 包含图中的所有顶点 ❖ 有且仅有n-1条边 本章不予 讨论的图