一、基本概念
1. 连通图与连通分量
1)连通图
无向图 G 中,如果从节点vi到vj有路径,则称节点vi和节点vj是连通的。若图中任意两个节点是连通的,则称G为连通图。
2)子图
图H(E'(H),V'(H))是图G(V(G),E(G))的子图,当且仅当V'(H)⊆V(G)且E'⊆E(G)。其中称G为H的母图,H为G的子图。记作H⊆G。
3)极大连通子图
图G的极大连通子图是图G的连通子图,如果再向其中加入一个节点,则该子图不连通。
4)连通分量
无向图G的极大通连子图被称为图G的连通分量。
任何连通图的连通分量只有一个,就是它本身;非连通图则有两个或两个以上连通分量。
在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,这些连通块就是连通分量(也叫连通分支)。无向图 G 的连通子图称为 G 的连通分量。
以上图为例,总共有四个连通分量,分别是:ABCD、E、FG、HI。
2. 强连通图与强连通分量
1)强连通图
有向图 G,若对图中的任意两个节点Vi、Vj,存在从 Vi 到 Vj 以及从 Vj 到 Vi 的路径,则称 G 为强连通图。
2)极大强连通子图
有向图G的极大强连通子图是图G的强连通子图,如果再向其中加入一个节点,则该子图不再是强连通的。
3)强连通分量
有向图G的极大强连通子图被称为图G的强连通分量。
强连通图只有一个强连通分量,即其自身,非强连通的有向图有两个或两个以上强连通分量。
以上图为例,总共有三个强连通分量,分别是:abe、fg、cdh
3. 无向图的桥与割点
4. 无向图的双连通分量