连通分量
连通分量
无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量。
定义
无向图的极大连通子图称为的连通分量( Connected Component)。任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量。
相关概念
路径
①无向图的路径:在无向图中,若存在一个顶点序列 使得 均属于 ,则称顶点 到 存在一条路径(Path)。
有向图的路径:在有向图中,路径也是有向的,它由 中的有向边 组成。
③路径长度:路径长度定义为该路径上边的数目。
顶点间的连通性
在无向图中,若从顶点 到顶点 有路径(当然从 到 也一定有路径),则称 和 是连通的。
连通图
若中任意两个不同的顶点 和 都连通(即有路径),则称为连通图(Connected Graph)。例如,图2是连通图。
强连通图
有向图中,若对于中任意两个不同的顶点 和 ,都存在从 到 以及从 到 的路径,则称是强连通图
强连通分量
有向图的极大强连通子图称为的强连通分量,强连通图只有一个强连通分量,即是其自身。非强连通的有向图有多个强连通分量
无向图简介
作为遍历图的应用举例,下面我们来讨论如何求图的连通分量。无向图中的极大连通子图称为连通分量。求图的连通分量的目的,是为了确定从图中的一个顶点是否能到达图中的另一个顶点,也就是说,图中任意两个顶点之间是否有路径可达。这个问题从图上可以直观地看出答案,然而,一旦把图存入计算机中,答案就不大清楚了。
对于连通图,从图中任一顶点出发遍历图,可以访问到图的所有顶点,即连通图中任意两顶点间都是有路径可达的。
对于非连通图,从图中某个顶点 出发遍历图,只能访问到包含顶点 的那个连通分量中的所有顶点,而访问不到别的连通分量中的顶点。这就是说,在连通分量中的任意一对顶点之间都有路径,但是如果 和 分别处于图的不同连通分量之中,则图中就没有从 到 的路径,即从 不可达 。因此,只要求出图的所有连通分量,就可以知道图中任意两顶点之间是否有路径可达。
参考资料
最新修订时间:2024-01-02 21:03
目录
概述
定义
相关概念
参考资料