连通图与连通分量在无向图中,若从顶点 v到顶点v有路径,则称顶点v与v2是连通 的。如果图中任意一对顶点都是连通的,则 称此图是连通图。非连通图的极大连通子 图叫做连通分量。 强连通图与强连通分量在有向图中,若对 于每一对顶点和v都存在一条从到y和 从v到v的路径,则称此图是强连通图。非 强连通图的极大强连通子图叫做强连通分 量 生成树一个连通图的生成树是其极小连 通子图,在n个顶点的情形下,有n-1条边。◼ 连通图与连通分量 在无向图中, 若从顶点 v1到顶点v2有路径, 则称顶点v1与v2是连通 的。如果图中任意一对顶点都是连通的, 则 称此图是连通图。非连通图的极大连通子 图叫做连通分量。 ◼ 强连通图与强连通分量 在有向图中, 若对 于每一对顶点vi和vj , 都存在一条从vi到vj和 从vj到vi的路径, 则称此图是强连通图。非 强连通图的极大强连通子图叫做强连通分 量。 ◼ 生成树 一个连通图的生成树是其极小连 通子图，在n个顶点的情形下，有n-1条边