基本概念
无向图
-
连通图和非联通图： 如果无向图 G 中任意一对顶点都是连通的，则称此图是连通图（connected graph）；相反，如
果一个无向图不是连通图，则称为非连通图（disconnected graph）。对非连通图G，其极大连通子图称为连通分量（connected component，或连通分支），连通分支数记为w(G)。 -
割顶集与连通度： 设V’是连通图G 的一个顶点子集，在G 中删去V’及与V’关联的边后图不连通，则称 V’ 是 G 的割顶集（vertex-cut set）。如果割顶集V’的任何真子集都不是割顶集，则称V’为极小割顶 集。顶点个数最小的极小割顶集称为最小割顶集。最小割顶集中顶点的个数，称作图G 的顶点连通度（vertex connectivity degree），记做κ(G)，且称图G 是κ–连通图（κ–connected graph）。
-
割点：如果割顶集中只有一个顶点，则该顶点可以称为割点（cut-vertex），或关节点。
-
点双连通图：如果一个无向连通图 G 没有关节点，或者说点连通度κ(G) > 1，则称 G 为点双 连通图，或者称为重连通图。
-
点双连通分量：一个连通图 G 如果不是点双连通图，那么它可以包括几个点双连通分量，也 称为重连通分量（或块）。一个连通图的重连通分量是该图的极大重连通子图，在重连通分量中不存在关节点。
-
割边集与边连通度：设 E’ 是连通图 G 的边集的子集，在 G 中删去E’后图不连通，则称E’是G 的割边集 （edge-cut set）。如果割边集 E’ 的任何真子集都不是割边集，则称 E’ 为极小割边集。边数最小的极 小割边集称为最小割边集。最小割边集中边的个数，称作图G 的边连通度（edge connectivity degree），记做λ(G)，且称图G 是λ–边连通图（λ–edge–connected graph）。
-
割边：如果割边集中只有一条边，则该边可以称为割边（bridge），或桥。
-
边双连通图：如果一个无向连通图 G 没有割边，或者说边连通度λ(G) > 1，则称G 为边双连通图。
-
边双连通分量：边双连通分量：一个连通图 G 如果不是边双连通图，那么它可以包括几个边双连通分量。一 个连通图的边双连通分量是该图的极大重连通子图，在边双连通分量中不存在割边。在连通图中， 把割边删除，则连通图变成了多个连通分量，每个连通分量就是一个边双连通分量。
-
顶点连通性与边连通性的关系：（顶点连通度、边连通度与图的最小度的关系） 设G 为无向连通图，则存在关系式：