1 基本概念
连通性是图论中描述结构整体关系的基础概念，核心问题是图中的各个顶点之间是否能够通过边所组成的路径相互到达。它不仅关心“能否到达”，也关心到达方式的数量、稳定性以及在局部删除元素后结构是否仍然保持完整。
1.1 图与连通性的定义
在图论中，图由顶点和边构成。若任意两个顶点之间都存在一条路径相连，则称该图具有连通性，或者直接称为连通图。若存在某些顶点对无法互相到达，则图为非连通图。连通性通常是研究图结构是否“整体成块”的首要标准。
1.2 可达性与路径
可达性是连通性的具体表现。若从顶点 \(u\) 出发可以沿着若干条边到达顶点 \(v\)，则称 \(u\) 到 \(v\) 可达。路径是实现可达性的基本对象，由一系列相邻顶点与边依次组成。图论中常通过路径长度、简单路径和回路等概念进一步分析连通关系。
1.3 连通图
连通图指任意两个顶点之间都存在路径的图。对于无向图，这是最常见的连通性概念；对于有向图，则需要结合方向进一步区分不同类型的连通。连通图在结构上通常被视为一个整体，适合用于描述网络、关系图和组合结构中的完整连通状态。
1.4 连通分量
当图不是整体连通时，可将其分解为若干个彼此独立的连通部分，这些部分称为连通分量。每个连通分量内部连通，而不同分量之间没有路径相连。连通分量为分析复杂图的局部结构提供了自然划分方式。
1.4.1 极大连通子图
极大连通子图是指在保持连通性的前提下，不能再加入其他顶点或边而仍保持连通的子图。它强调“最大程度地扩展”而不是“包含尽可能多的边”。在无向图中，连通分量正是图的极大连通子图。
1.4.2 分量划分
分量划分是将非连通图按连通关系拆分为若干连通分量的过程。每个顶点恰好属于一个分量，不同分量之间相互独立。该划分具有唯一性，因此常用于图的结构分析和算法预处理。
2 连通性的分类
连通性在不同类型的图中表现并不相同。无向图强调双向可达，有向图则需要考虑边的方向限制，而某些特殊图类由于结构固定，其连通性也具有更明确的性质。
2.1 无向图中的连通性
在无向图中，边没有方向限制，因此任意路径上的行进都不受方向约束。无向图的连通性定义最为直接，通常也是连通理论的基础模型。只要图中任意两点之间存在无向路径，就认为图连通。
2.1.1 单连通与多连通
单连通通常指图恰好处于一个连通整体中，没有被进一步拆成多个分量。多连通则强调图内存在多条独立连接方式，或在更宽泛的语境下指图中存在多个可分析的连通结构。在一些非正式表述里，这类说法往往侧重结构是否具有冗余连接。
2.1.2 孤立点与孤立边
孤立点是指没有与任何边相连的顶点，它单独构成一个连通分量。孤立边则通常指只连接两个低度顶点、并在局部上不与更复杂结构相连的边。它们都反映了图中的局部弱连接状态，对整体连通性有直接影响。
2.2 有向图中的连通性
有向图中的边带有方向，因此连通性需要区分“沿方向可达”与“忽略方向可达”。这使得有向图的连通性比无向图更细致，也更适合表示流程、依赖关系和单向传播结构。
2.2.1 弱连通
若将有向图中的边视为无向边后得到的图是连通的，则原图称为弱连通。弱连通只关注底层结构是否连成一片，不要求方向上彼此都能到达。它是有向图连通性的较宽松形式。
2.2.2 强连通
若有向图中任意两个顶点之间都能沿着有向路径相互到达，则称其为强连通图。强连通要求方向上的双向可达性，因此比弱连通更严格。强连通分量是有向图分析中的重要结构单元。
2.2.3 单向可达结构
单向可达结构指从某些顶点可以到达另一些顶点，但反向并不可达的情形。这类结构常见于层次关系、流程图和状态转移系统中。它说明图具有明显的方向性，不一定形成强连通，却可能在局部呈现有序传播。
2.3 特殊图类中的连通性
某些图类因构造方式固定，其连通性具有较强规律。例如树总是连通但无回路，完全图天然高度连通，而二分图则通过顶点分组方式体现不同的连接模式。
2.3.1 树与森林
树是连通且无环的无向图，具有最基本的连通结构。森林由若干棵树组成，因此通常是非连通的，但其每个连通分量都为树。树和森林常用于体现“连通但稀疏”与“分离但有序”的两种极端结构。
2.3.2 完全图
完全图中任意两个不同顶点之间都直接相连，因此具有最强的连通性之一。即使删去少量边，图通常仍保持连通。完全图常作为理论上的极端模型，用于比较其他图的连通稳健程度。
2.3.3 二分图
二分图的顶点可划分为两个互不相交的集合，边只连接不同集合中的顶点。其连通性取决于具体边集的分布。若二分图连通，则它在结构上常表现为两类对象之间的匹配或交互关系。
3 结构性质与判定
连通性不仅是一个状态描述，也是一类可分析、可判定的结构性质。通过研究关键顶点和关键边，可以衡量图对删除操作的敏感程度，从而判断其稳健性。
3.1 割点与桥
割点和桥是破坏连通性的两类典型“关键元素”。前者是顶点层面的薄弱环节，后者是边层面的薄弱环节。它们在网络脆弱性分析中非常重要。
3.1.1 割点的定义与作用
割点是指删除该顶点及其关联边后，会使图的连通分量数量增加的顶点。它表明该点在结构中起到“枢纽”作用。一旦割点失效，图可能被分成多个互不相连的部分。
3.1.2 桥的定义与作用
桥是指删除该边后会使图的连通分量数量增加的边。它代表某种唯一通道或关键连接。桥的存在意味着相应局部没有冗余路径，因而容易形成连接瓶颈。
3.2 点连通度
点连通度用于衡量图在顶点删除下保持连通的能力。它反映图对顶点失效的抵抗程度，数值越大，说明图越不容易因少数顶点的移除而解体。
3.2.1 顶点删除与连通性破坏
顶点删除是检验图鲁棒性的基本操作。若删去某些顶点后图仍连通，说明原图具有较好的冗余结构；若很容易被拆开，则说明顶点之间依赖性较强。点连通度正是对这种现象的量化。
3.2.2 最小割点集
最小割点集是指删去后能使图不连通的最小顶点集合。它是点连通度的核心对象，体现了图中最薄弱的顶点组合。研究最小割点集有助于定位网络中的关键节点群。
3.3 边连通度
边连通度衡量图在边删除下保持连通的能力。与点连通度相比，它更侧重连接通道本身的冗余程度，常用于分析链路失效后的影响。
3.3.1 边删除与连通性破坏
删除边会削弱顶点之间的联系，但不一定立刻导致图分裂。若图中存在多条替代路径，则某些边的失效影响较小；反之，一条边即可决定局部连通状态。边连通度用于描述这种抗破坏能力。
3.3.2 最小割边集
最小割边集是删去后能够破坏连通性的最小边集合。它揭示了图中最小规模的关键通道组。与割点集类似，这一概念常用于寻找结构中的瓶颈边和脆弱链路。
3.4 k-连通性
k-连通性是对连通强度的分级描述。它要求图在删去少于 \(k\) 个顶点或边后仍保持某种连通性，因此是衡量网络冗余和容错能力的重要指标。
3.4.1 2-连通图
2-连通图通常指删除任意一个顶点后仍保持连通的图，等价地说，它没有割点。此类图比一般连通图更稳固，最小程度上避免了单点失效导致整体分裂。
3.4.2 3-连通图
3-连通图要求删去任意两个顶点后图仍保持连通。它比2-连通图更强，体现更高层次的结构冗余。3-连通图在平面图、网络设计和结构分解中具有重要作用。
3.4.3 高阶连通性
高阶连通性指将上述要求推广到更大的 \(k\)。随着 \(k\) 增大，图的结构约束更严格，但稳定性也更高。高阶连通分析常用于衡量大规模网络的容错能力和多路径保障能力。
4 连通性的表示与证明
连通性不仅可以从结构上定义，也可以通过矩阵、表和遍历算法加以表示和验证。证明连通性时，常见方法包括直接构造、反证和归纳等。
4.1 邻接矩阵与连通性
邻接矩阵用矩阵形式记录顶点之间是否存在边。通过矩阵幂或可达闭包等方式，可以分析任意两点之间是否存在路径。它适合进行理论推导和代数化处理。
4.2 邻接表与遍历
邻接表按顶点列出其相邻顶点，便于进行深度优先搜索和广度优先搜索。对于稀疏图，邻接表通常更节省空间，也更适合实际连通性判定。
4.3 深度优先搜索
深度优先搜索通过沿着一条路径尽可能深入地访问图中顶点，可用于判断图是否连通、求连通分量以及寻找割点和桥。它在连通性分析中具有较高的通用性和效率。
4.4 广度优先搜索
广度优先搜索按层次逐步扩展访问范围，适合发现从起点出发的可达区域。它不仅能判断连通性，还能给出最短路径层数，在无权图分析中尤其常用。
4.5 连通性证明方法
证明连通性时，除了算法验证，还常采用数学证明方式。这些方法往往从路径存在性、结构矛盾或规模递推入手，适合处理一般性结论。
4.5.1 构造路径法
构造路径法是直接给出任意两点之间的一条路径，从而证明图连通。该方法直观清晰，常用于具体图或具有规则结构的图类。
4.5.2 反证法
反证法通常假设图不连通，然后推出与已知性质矛盾的结论。它适合证明“必然连通”类命题，尤其在结合极值条件或结构约束时效果明显。
4.5.3 归纳法
归纳法通过从小规模图出发，逐步推广到一般情形，常用于证明随顶点数增加而保持连通的结构性质。它在树、网格和递推构造图中很常见。
5 相关定理与性质
连通性与若干经典定理紧密相关，这些定理从度数、路径独立性和特殊图性质等角度揭示了图结构的内在规律。
5.1 握手定理与连通结构
握手定理指出，图中所有顶点度数之和等于边数的两倍。虽然它并不直接给出连通性结论，但能反映顶点连接的整体分布。通过度数总量，可以间接分析图是否可能形成孤立部分或稀疏薄弱区域。
5.2 连通图的基本性质
连通图至少包含一条覆盖所有顶点的路径关系链。若图连通，则其任意生成树也连通；若图有多个连通分量，则每个分量都可单独研究。连通性还与最小边数、生成树和图的直径等性质密切相关。
5.3 Menger定理
Menger定理是连通性理论中的核心结果之一，说明顶点或边之间的独立路径数与相应的割集规模之间存在紧密对应。它把“有多少条不相交的路”与“需要删掉多少点或边才能阻断”联系起来。
5.3.1 点版本
点版本的 Menger 定理讨论两点之间的内部点不相交路径数量，等于分隔这两点所需删除的最小中间顶点数。它揭示了点层面上的连通冗余关系。
5.3.2 边版本
边版本讨论边不相交路径数量与最小割边集大小之间的关系。它常用于网络通道设计，因为边不相交路径越多，说明链路冗余越强，抗故障能力越高。
5.4 Euler图与Hamilton图中的连通条件
Euler图要求图连通，并且满足所有顶点度数的特定奇偶条件，才能存在经过每条边恰好一次的闭迹。Hamilton图则要求存在经过每个顶点恰好一次的回路，连通性是其基本前提之一，但仅有连通性并不足以保证存在 Hamilton 回路。
6 算法与应用
连通性研究不仅是理论图论的一部分，也是许多算法与应用系统的基础。实际问题中，往往需要快速判断图是否连通、找到薄弱环节或评估网络可靠度。
6.1 连通分量算法
连通分量的求解是图算法中的基础任务。常见方法包括深度优先搜索和广度优先搜索，它们能够在遍历过程中标记所属分量并输出分量划分结果。
6.1.1 DFS求分量
DFS求分量时，从一个未访问顶点出发，将所有可达顶点递归或栈式访问并标记为同一分量。完成一次搜索后，再从下一个未访问顶点继续，直到所有顶点都被处理完毕。
6.1.2 BFS求分量
BFS求分量通过队列逐层访问所有相邻顶点，并将访问到的顶点归入同一连通分量。它实现简单，适用于需要按层次展开的图遍历任务。
6.2 最小割与最大流
最小割与最大流理论常用于分析网络中的瓶颈位置。最小割描述将网络分成两部分所需切断的最少容量，而最大流则寻找可从源点输送到汇点的最大总量，两者在理论上存在深刻联系。
6.2.1 网络可靠性分析
在通信和运输网络中，连通性决定信息或资源能否顺利传递。通过寻找关键点、关键边以及最小割，可以评估网络在局部失效情况下的可靠程度。
6.2.2 割集优化
割集优化关注如何以尽可能小的代价切断特定连接，或如何设计结构使其更难被切断。它广泛用于网络规划、故障隔离和资源分配问题。
6.3 应用场景
连通性在许多实际系统中都有对应模型，既适合描述物理连接，也适合表示逻辑关系。其应用范围从基础计算结构延伸到复杂关系网络。
6.3.1 通信网络
在通信网络中，连通性决定节点之间的信息传输是否可行。冗余路径越多，网络越不容易因单点失效而中断，因此连通性是网络设计的重要指标。
6.3.2 社交网络
社交网络常以图结构表示人与人之间的关系。连通分量可以反映群体圈层，割点则可能对应“桥梁式人物”，有助于分析信息传播和群体分化现象。
6.3.3 计算机网络
计算机网络中的连通性涉及主机、路由器和链路之间的互联状态。通过图模型可以分析路由可达性、容错路径以及故障恢复能力。
6.3.4 组合设计与图建模
在组合设计中，连通性可用于构造实验方案、资源分配模型和约束关系图。通过合适的图建模，复杂对象之间的相依关系能够被更清楚地表示出来。