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