图连通性

连通性把许多局部边串成一个全局问题：能否从任意顶点沿若干步到达任意另一顶点。可达关系自动生成分量，无需人为切块；一条跨越两个候选块的边会立刻把它们合并。

这个性质只问“至少有一条路”，没有衡量替代路线。两个稠密区域用一条桥连接时，整图仍然连通，却把全部跨区通信押在单条边上。点连通度、边连通度和扩张率会继续量化这种脆弱性，本页只建立零与非零之间的第一道界线。

加边不会拆散已有分量，只会保持或合并分量；删边则可能让一个分量裂开。这种单调方向解释了为什么只增边的在线维护很容易，而允许删除后需要更丰富的数据结构。

取两个三角形 $abc$ 与 $def$，先不连边。从 $a$ 出发的搜索只能发现 $a,b,c$，再从未访问的 $d$ 出发才发现 $d,e,f$，所以有两个分量。加入边 $cd$ 后，从 $a$ 沿 $a,c,d,e$ 即可到达另一边，两个分量合为一个；这就是“哑铃图”。删掉 $cd$，分量数又从 $1$ 变为 $2$，故 $cd$ 是桥。

若改为让两个三角形共享一个顶点，图仍连通且没有桥：每条边都有三角形的另外两边可绕行。但删除共享顶点会断开图。因此抵抗一条边失效和抵抗一个顶点失效是两种不同要求。

最小度至少为一不能保证连通。两个互不相交的圈中，每个顶点度数都是二，整图仍有两个分量。反过来，孤立顶点度数为零，却会独自形成一个合法的单点连通分量。

若 $G$ 有 $n$ 个顶点且连通，则 $|E|\ge n-1$。从任一顶点开始探索，每发现一个新顶点，至少要使用一条从已发现集合跨出的新边；记录首次发现边得到一棵含 $n-1$ 条边的生成树。达到等号时没有额外边，因而 $G$ 本身是一棵树。

对有向图理路有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。，忽略箭头后连通称为弱连通；任意两点沿箭头双向互达称为强连通。单向链的无向骨架连通，却只有单点强连通分量，不能把无向定义直接搬过去。

广度优先搜索理路广度优先搜索Breadth-first search · BFS按无权距离分层访问可达顶点的图遍历算法。或深度优先搜索理路深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。从顶点 $s$ 出发，恰好访问 $s$ 所在分量。对每个尚未访问的顶点重新启动一次搜索，即可在 $O(|V|+|E|)$ 时间枚举全部分量，并以首次发现边输出生成森林。

BFS 额外保留无权最短距离的层次；DFS 形成适合 low 值、割点和桥分析的深度树。两者都能判连通，但中间证书不同。生成树理路生成树Spanning tree包含原图全部顶点且自身为树的子图。是连通性的紧凑正证书，而把顶点分为两个非空集合且证明没有跨集合的边，则是不连通的证书。要求两侧非空很关键，否则任何图都能用空集和全体顶点给出无意义的“划分”。

若边只会插入，并查集理路并查集Disjoint-set union · Union-find维护不交集合划分并支持合并与代表元查询的数据结构。可为每个分量维护代表元：新边两端属于不同集合时执行合并。它不保存集合内部的完整路径结构，所以删除一条边后无法判断原集合是否应裂成两块；全动态连通需要另外的更新机制。

割点与桥理路割点与桥Cut vertex and bridge删除后增加连通分量数的顶点或边。定位单个失效点，Menger 定理理路Menger 定理Menger's theorem两点间内部顶点不交路径的最大条数等于分离两点所需删去的最少顶点数。用不交路径数刻画更高阶连通，图 Laplacian理路图 LaplacianGraph Laplacian · Laplacian matrix用度矩阵减邻接矩阵得到的算子，以二次型衡量相邻顶点取值的不一致。则把分量数编码为零特征值的重数。这些后继从组合、极值和代数三个方向细化同一个可达划分。