有向连通图,非连通简单无向图

有向连通图,非连通简单无向图

连通图：无向图中，如果任意两点是连通的，那么图被称作连通图。有向图：弱连通：有向图的底图(无向图)是连通图，则是弱连通图。单向连通：有向图中，任意结点对中，至少从一个到另一个是强连通图定义：在有向图G中，如果任意两个不同的顶点相互可达，则称该有向图是强连通的。举个例子：下图有三个子图(强连通分量):{1,4,5},{2,3}, 求强连通分量的作用：把有向图中具有相同

1.连通图和连通分量连通图：无向图中，如果顶点vi到vj有路径，则称vi和vj是连通的。如果图中任何两个顶点都是连通的，则称G为连通图。如下图连通图连通分量：无向图G的极大连通子图称强连通图有向图中，若任意两个顶点Vi 和Vj,满足从Vi 到Vj 以及从Vj 到Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图。如图4 所示就是一个强连通图。

在有向图G中，如果两个顶点间至少存在一条互相可达路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连导出子图G[V_1],G[V_2],\dots,G[V_k] ,称为G 的连通分支，其个数记为\omega(G)。例2:下图中，a)为无向连通图，\omega(G)=1;(b)为无向非连通图，\omega(G)=3。3.推论无向连通图