然而在所有的连通图中它们的连通程度是很不相同的

然而在所有的连通图中它们的连通程度是很不相同的图论·点连通度、边连通度及其关系Contents目录图连通度的基本概念、计算方法与核心定理01基本概念与知识储备02点连通度的定义与计算03边连通度的定义与计算04连通度之间的深层关系05充分条件与重要定理CHAPTER01基本概念与知识储备回顾连通图、割点、割边与块的基本定义GraphTheory从连通性到连通度：问题的提出图的连通性可以将图分为连通图与非连通图两大类，但连通图之间的"连通程度"存在显著差异。我们需要一种量化工具来衡量这种差异，这就是"连通度"概念产生的动机。连通图与非连通图·黑板教学示意01连通图的定义：图G中任意两个顶点u和v之间都存在路径（链），则称G为连通图，否则为非连通图。02连通性的分类功能：利用连通性可以将所有图划分为连通图和非连通图两大类别。03问题的提出：在所有连通图中，它们的连通程度是很不相同的——需要更精细的量化工具。04连通度的意义：连通度通常代表网络的稳定程度，连通度越好的图所代表的网络越稳定。GraphConnectivity核心前置概念：割点、割边与块割点和割边是刻画图"脆弱性"的基本工具。块是不含割点的极大连通子图，代表图中最"坚固"的局部结构。点割集和边割集则提供了使图不连通的最小"破坏"方案的量化基础。CUTVERTEX&CUTEDGE割点与割边割点(CutVertex)：删去结点x后图的连通分支数增加，即ω(G−x)>ω(G)，则x为割点割边(CutEdge/桥)：删去边e后图的连通分支数增加，即ω(G−e)>ω(G)，则e为割边割点和割边本质上标识了图结构中最"脆弱"的环节，是理解连通度的出发点BLOCK&CUTSET块与割集块(Block)：没有割点的非平凡连通图，或G中不含割点的极大连通子图点割(VertexCut)：顶点集真子集T使G−T不连通或为平凡图，则T为G的点割边割(EdgeCut)：边集真子集S使G−S不连通或为平凡图，则S为G的边割Chapter02点连通度的定义与计算用最小顶点割的规模量化图的顶点连通程度GRAPHCONNECTIVITY点连通度的严格定义点连通度κ(G)是使连通图G变得不连通或退化为平凡图所需删除的最少顶点数。它等于G的最小点割的基数，对于完全图Kₙ特殊定义为κ(Kₙ)=n−1，取值范围为0≤κ(G)≤n−1。01定义设G是连通图，κ(G)=min{|T|:T是G的点割}，称为G的点连通度（vertexconnectivity）。02特殊约定若G为完全图Kₙ，则定义κ(Kₙ)=n−1，因为完全图不存在通常意义的点割。03取值范围对于n阶连通图，点连通度满足0≤κ(G)≤n−1。0≤κ(G)≤n−104物理含义κ(G)表示要使图G不连通，至少需要同时"攻击"多少个顶点。RobustnessMeasureGraphTheory·VertexConnectivity点连通度的计算实例通过不同类型的图可以清晰看到点连通度的差异：链状图仅需删除1个顶点即可断开（κ=1），环状图需删除2个顶点（κ=2），而完全图Kn需要删除n-1个顶点（κ=n-1）。这直接体现了"连通程度很不相同"的核心命题。链状图最小顶点割仅含1个顶点，删除该割点后图分为两个连通分支，是连通程度最弱的结构κ=1环状图最小顶点割含2个顶点，需同时删除两个不相邻顶点才能断开，连通性优于链状结构κ=2完全图K₅不存在传统点割，按约定κ(K₅)=5−1=4，任意两点间均有边相连，体现最高连通程度κ=4对比结论三个图均为连通图，但κ值分别为1、2、4，连通程度存在本质差异，点连通度是量化连通性强弱的关键指标EssentialDifferenceGRAPHTHEORYn-连通图的定义与等价刻画n-连通图是连通度κ(G)≥n的图，代表了一种"至少需要n次攻击才能破坏连通性"的鲁棒性。2-连通图具有特别优美的等价刻画：任意两个不同顶点都被两条内部不交的路径所连接，保证了路径的冗余性。DEFINITIONn-连通图定义若无向图G的连通度κ(G)≥n，则称G为n-连通图(n-connectedgraph)。连通度κ(G)定义为使G不连通或成为平凡图所需删除的最少顶点数，它精确刻画了图的结构稳定性。κ≥nEQUIVALENCE2-连通图等价条件阶≥3的简单图G是2-连通的⟺任两个不同顶点被两条内不交的路所连接。这一刻画揭示了2-连通图的本质特征：任意两点间存在冗余路径，网络具有容错能力。κ≥2CONCEPT内不交路定义一族路中任意两条路除起点与终点外没有公共顶点。内不交性是路径独立性的体现，确保多条路径之间互不干扰，是构造可靠通信网络的重要拓扑性质。V∩V'=∅THEOREM回路刻画G是2-连通的⟺任两个不同顶点含在G的某一个回路上。回路刻画表明2-连通图中不存在割点，任意两点都位于某个环上，体现了图的高度循环连接特性。CYCLEChapter03边连通度的定义与计算用最小边割的规模量化图的边连通程度EDGECONNECTIVITY边连通度的严格定义边连通度λ(G)是使连通图G变得不连通所需删除的最少边数，等于最小边割的基数。与点连通度形成自然对偶：点连通度关注"删除顶点"的破坏成本，边连通度关注"删除边"的破坏成本。01严格定义λ(G)设G是连通图，λ(G)=min{|S|:S是G的边割}，称为G的边连通度。边割是指删除后使图不连通的边集，边连通度即最小边割的大小02最小边割λ-割若S是G的一个λ(G)-边割，则称S是G的一个最小边割。最小边割是达到边连通度临界值的边集，具有最优性03完全图约定n−1λ(Kn)=n−1，与点连通度的特殊处理方式一致。n阶完全图每对顶点间均有边相连，需删除n−1条边才能破坏连通性04物理含义CUTλ(G)表示要切断图G的连通性，至少需要同时"切断"多少条边。边连通度越大，网络对边故障的容错能力越强，可靠性越高EdgeConnectivity·Examples边连通度的计算实例与对比边连通度的计算表明，在某些图中λ(G)>κ(G)——删除边比删除顶点更难破坏连通性。这揭示了"破坏顶点"通常比"破坏边"更高效，因为删除一个顶点会同时移除所有与之关联的边。01链状图最小边割仅含1条割边，删除后图分为两个连通分支。这是边连通度最低的图结构，任何一条边都是关键连接。单边即可断开λ=102环状图最小边割含2条边，需同时删除两条边才能断开环路。环形结构提供了冗余路径，增强了连通可靠性。需双边才能断开λ=203蝴蝶图κ=1（存在割点），但λ=2（需删2条边）。这是典型的λ(G)≥κ(G)实例：删除中心顶点可立即断开图，而删除单条边无法做到。点连通<边连通κ=1λ=204n-边连通图若λ(G)≥n则称G为n-边连通的。这是比n-连通更弱的条件——仅要求删除足够多的边才能断开，而非删除顶点。边容错性度量标准λ≥nGraphTheory·Connectivity定理：2-边连通图的强连通定向若G是2-边连通图，则G必存在强连通的定向图。这意味着我们可以为无向的2-边连通网络中的每条链路指定方向，使得网络中任意两个节点之间仍能双向通信——这在交通网络和通信网络设计中具有重要的应用价值。01定理陈述若G是2-边连通图，则G有强连通的定向图——即可以给每条边定向，使得结果有向图强连通。02必要性图G有强连通定向图的必要条件是G为2-边连通的，否则G中存在割边将导致单向不可达。03构造性证明思路从G的一个圈开始定向为有向圈，逐步通过边不重路将新顶点加入并合理定向。04应用价值为城市单行道规划、通信网络链路方向设计提供理论保证。CHAPTER04连通度之间的深层关系揭示点连通度、边连通度与最小度之间的不等式链与等式条件CoreTheorem·GraphConnectivity核心定理：κ(G)≤λ(G)≤δ(G)对任何简单图G，点连通度、边连通度与最小度之间成立经典不等式链κ(G)≤λ(G)≤δ(G)。这揭示了三种图参数的层级关系：删除顶点比删除边更"高效"，而最小度给出了连通度的上界。01不等式链：对任何简单图G，κ(G)≤λ(G)≤δ(G)，其中δ(G)为图G的最小顶点度。该不等式建立了图连通性的基本度量框架。κ≤λ≤δ02证明λ≤δ：取最小度顶点x，与x关联的δ(G)条边构成一个边割，故λ(G)≤δ(G)。此证明直接且构造性强。λ≤δ03证明κ≤λ：利用归纳法，设S为最小边割，G−S恰有两个连通分支，通过构造点割完成证明。核心在于边割与点割的转化。κ≤λ04直观理解：删除一个顶点会同时删除其所有关联边，所以"攻击"顶点比"攻击"边效率更高。这一直观解释了为何κ通常更小。κ≤λConnectivityTheory不等式链的紧致性与差距分析κ(G)≤λ(G)≤δ(G)中每个不等号都可以严格成立，且差距可以任意大——但当最小度足够大（δ≥⌊n/2⌋）时，边连通度会"追上"最小度。差距可任意大对任意整数a≤b≤c（a>0），存在图G使得κ(G)=a，λ(G)=b，δ(G)=cκ=a·λ=b·δ=c不受限制的差距κ和λ、λ和δ之间的差距不受限制，可以构造出差距任意大的例子gap→∞Whitney条件若G为n阶简单图且δ(G)≥⌊n/2⌋，则λ(G)=δ(G)，边连通度等于最小度δ≥⌊n/2⌋核心启示当图中每个顶点都有足够多的邻居时，边连通度达到其理论上界λ(G)=δ(G)GraphTheory·Connectivity典型图的连通度参数对比不同类型图的三参数表现出不同的关系模式：路径图和圈图三者相等，完全图三者均取最大值n-1，而某些特殊构造的图可以精确实现任意给定的κ<λ<δ组合，展示了图结构的丰富多样性。01路径图Pn（n≥3）κ=1，λ=1，δ=1，三参数完全相等，连通度最低κ=λ=δ=102圈图Cn（n≥3）κ=2，λ=2，δ=2，三者相等但高于路径图，体现环状结构的鲁棒性κ=λ=δ=203完全图Knκ=n-1，λ=n-1，δ=n-1，三参数均取最大可能值，是"最连通"的图κ=λ=δ=n−104推论2.3.7设G为n阶简单图，若δ(G)≥⌊n/2⌋，则λ(G)=δ(G)δ≥⌊n/2⌋PROOFSTRATEGY推论2.3.7的证明思路分析推论2.3.7的核心证明策略是：设最小边割将图分为两个连通分支G1和G2，通过分析G1中各顶点的度数分配（内部边vs.跨割边），利用δ(G)≥⌊n/2⌋的条件约束跨割边的数量下界，从而证明λ(G)=δ(G)。STEP01设定最小边割设S是G的最小边割，G-S恰好有两个连通分支G₁和G₂，点数分别为n₁和n₂，n₁≤n₂最小边割STEP02分析度数总和分析G₁中各顶点在G中的度数总和：部分边贡献给G₁内部连接，部分边属于边割S度数分配STEP03约束跨割边数利用δ(G)≥⌊n/2⌋条件，G₁中每个顶点至少有⌊n/2⌋条关联边，扣除内部边后剩余即跨割边跨割边下界STEP04推导最终等式通过度数不等式推导得出|S|≥δ(G)，结合λ(G)≤δ(G)得到λ(G)=δ(G)λ(G)=δ(G)Chapter05充分条件与重要定理通过度数条件保证图的连通度——Ore型定理与推广GRAPHCONNECTIVITYOre型充分条件（一）：不相邻顶点度数之和若n阶简单图G中任意两个不相邻顶点u和v都满足d(u)+d(v)≥n-1，则G具有较高连通度。01Ore型条件设G是n阶简单图，若对任意两个不相邻顶点u和v，都有d(u)+d(v)≥n-1d(u)+d(v)≥n-102高连通度结论满足上述条件的图G具有较高的点连通度，保证图不会轻易被少数顶点割断κ(G)高连通03直觉理解不相邻顶点度数之和大意味着即使不直接相连，它们也各自拥有大量邻居，增加了"绕行"路径绕行路径04与最小度条件的比较Ore型条件比δ(G)≥⌊n/2⌋更精细，因为它只约束不相邻顶点对而非所有顶点δ(G)≥⌊n/2⌋GraphTheory·DegreeConditionsOre型充分条件（二）：四顶点推广定理定理2.3.5将Ore型条件从"两个不相邻顶点"推广到"任意四个顶点"的度数约束，在更弱假设下推导出同样强的连通度结论。01定理2.3.5核心陈述设G是n阶连通简单图，若对任意四个顶点满足特定度数条件，就有相应的连通度结论成立02推广思路从约束两个不相邻顶点到约束四个顶点，条件形式更灵活，适用范围更广03证明技术运用路径扩展技术和度数列分析方法，比两顶点情形的证明更为精细04方法意义展示了度数条件方法的深刻性——更弱的假设可以得到同样强的结论Summary课程总结：连通度知识体系本课程系统建立了图连通度的理论框架：从点连通度和边连通度的定义出发，通过核心不等式链κ≤λ≤δ揭示三者关系，最终用Ore型充分条件展示了如何从度数信息推断连通度，形成了"定义→关系→应用"的完整知识闭环。定义层点连通度κ(G)：最小点割基数，衡量删除顶点的破坏成本边连通度λ(G)：最小边割基数，衡量删除边的破坏成本两者共同量化了连通图的"连通程度"差异κ(G)·λ(G)关系层核心不等式链：κ(G)≤λ(G)≤δ(G)对任何简单图成立差距可任意大：对任意a≤b≤c存在图使κ=a、λ=b、δ=c紧致条件：δ(G)≥⌊n/2⌋时λ(G)=δ(G)κ≤λ≤δ应用层Ore型充分条件通过不相邻顶点度数之和保证连通度四顶点推广定理在更弱假设下得到同样强的结论2-边连通图必存在强连通定向图，具有网络设计应用价值Ore定理APPLICATION连通度的实际应用：网络可靠性分析在通信网络和交通网络研究中，图的连通度被解释为网络的可靠程度。点连通度对应"至少摧毁多少节点才能使网络瘫痪"，边连通度对应"至少切断多少链路才能使网络断开"，是网络韧性设计的核心指标。通信网络基础设施·基站与信号塔通信网络：κ(G)表示至少需摧毁多少个中继节点才能使网络中某对节点失去通信能力κ(G)交通网络：λ(G)表示至少需封锁多少条道路才能使路网中某两地之间不可达λ(G)电力网络：高连通度保证局部故障不会导致大面积停电，提升电网的容错能力FAULTTOLERANT设计原则：关键基础设施网络的连通度设计需要平衡建设成本与系统可靠性需求COSTvsRELIABILITYALGORITHM连通度的计算方法图的连通度可以通过最大流最小割定理进行算法计算。核心思想是将"寻找最小点割/边割"转化为网络流问题：通过顶点拆分技巧将点连通度计算转化为标准最大流问题，边连通度则可直接应用最大流算法。顶点拆分技巧将每个顶点x拆分为x'和x''，中间连容量为1的边，将点割问题转化为边割问题。x→x'x''点连通度计算对每对不相邻顶点构造流网络求最大流，取所有结果的最小值即为κ(G)。κ(G)边连通度计算固定一个顶点s，对所有其他顶点t求s-t最小割，取最小值即为λ(G)。λ(G)时间复杂度基于最大流算法，可在多项式时间内完成连通度的精确计算。Poly-timeGraphConnectivityTheoryMenger定理：连通度的理论基石Menger定理揭示了"最小割集"与"最大不交路径族"之间的对偶关系：分离两个顶点所需的最少元素数等于连接它们的不交路径的最大条数。这一定理是连通度理论的基石，也是最大流最小割定理在图论中的先驱。顶点版本分离不相邻顶点u和v所需的最少顶点数，等于u到v的内部不交路径的最大条数。该版本刻画了图的点连通度，是网络可靠性分析的理论基础。边版本分离u和v所需的最少边数，等于u到v的边不交路径的最大条数。边版本与网络流理论紧密相关，为最大流算法提供了组合解释。对偶本质"最小破坏"（割集）与"最大冗余"（不交路径族）之间存在精确的对偶等式。这种对偶性体现了组合优化中极值结构的深刻统一，具有普适的数学美感。理论地位Menger定理是图论中最重要的定理之一，是后续最大流最小割定理的思想源头。它在网络设计、容错计算和组合优化等领域具有广泛而深远的应用价值。GRAPHPARAMETERS连通度与其他图参数的关系连通度与图的直径、围长、色数等参数之间存在深层关联。多维度参数的交叉分析有助于全面刻画图的拓扑特征。直径与连通度直径为2的图通常连通度较高，任意两顶点距离不超过2，结构紧凑，信息传递效率高。直径D=2围长与连通度大围长图局部偏树状，缺少短圈冗余路径，连通度往往较低，容错能力相对有限。特征Tree-like色数与连通度高色数图通常较稠密，可能连通度较高，但两者无直接蕴含关系，需具体分析。色数χ(G)综合视角连通度、直径、围长等多维度参数综合分析，方能全面刻画图结构的拓扑特性。方法Multi-dimCONNECTIVITYANALYSIS特殊图类的连通度分析许多具有高度对称性的特殊图类满足κ(G)=λ(G)=δ(G)，即不等式链中所有等号同时成立。这些"最优连通"的图在互连网络设计中具有重要应用。完全二部图Km,n的点连通度和边连通度均等于min(m,n)，由较小一侧的顶点数决定当m≠n时δ(G)=min(m,n)仍成立，故κ=λ=δ=min(m,n)Km,n超立方体QnQn是n-正则图，δ=n，且κ=λ=n，三参数完美相等超立方体是最优连通图，广泛应用于并行计算的互连网络拓扑设计QnPetersen图Petersen图是3-正则图，κ=λ=δ=3，是经典的最优连通图实例作为图论中最重要的反例图之一，展示了3-连通图的丰富结构特性κ=3GRAPHTHEORY·CONNECTIVITYHarary图：最少边数的k-连通图Harary图Hk,n是在给定顶点数n和连通度要求k的前提下，边数最少的k-连通图。它代表了实现指定连通度的"最优网络设计"——用最少的连接资源达到所需的可靠性水平，对网络拓扑优化具有直接的指导意义。定义Harary图Hk,n是满足κ(G)≥k且边数最少的n阶图，是连通度的"最优设计"问题κ(G)≥k构造方法k为偶数时，每个顶点与环上其两侧各k/2个顶点相连，形成均匀对称的连接结构k偶数构造边数下界Hk,n的边数恰好为⌈kn/2⌉，给出了实现k-连通所需最少连接的理论答案⌈kn/2⌉工程意义在设计通信网络时，Harary图给出了达到指定可靠性所需最少链路数的参考方案NETWORKDESIGNGRAPHCONNECTIVITY块分解与图的连通结构分析块分解将图分解为不含割点的极大连通子图（块），通过块-割点树完美刻画图的全局连通结构。每个块是图中的'刚体'（内部高度连通），割点是连接不同块的'关节'（连通性的薄弱环节）。块的性质每个块要么是2-连通图，要么是一条边K₂，要么是孤立点K₁2-连通块-割点树以块和割点为节点构成的树结构，完整描述图的全局连通拓扑块-割点树连通度含义图的点连通度κ(G)=1当且仅当G有割点，即G由多于一个块组成κ(G)=1结构洞察块分解揭示了图哪些部分"坚固"（块内部）、哪些部分"脆弱"（割点处）坚固vs脆弱GRAPHCONNECTIVITY典型图类连通度参数汇总通过对比不同图类的三参数(κ,λ,δ)可以发现：高度对称的图类通常满足κ=λ=δ（最优连通），而某些非对称构造可使不等式严格成立。各类图的点连通度κ、边连通度λ与最小度δ对比