下载文档原格式
连通图的割点、割边(桥)、块、缩点，有向图的强连通分量一、基本概念无向图割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。
块：没有割点的连通子图割边：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。
缩点：把没有割边的连通子图缩为一个点，此时满足任意两点间都有两条路径相互可达。
求块跟求缩点非常相似，很容易搞混，但本质上完全不同。
割点可以存在多个块中(假如存在k个块中)，最终该点与其他点形成k个块，对无割边的连通子图进行缩点后(假设为k个)，新图便变为一棵k个点由k-1条割边连接成的树，倘若其中有一条边不是割边，则它必可与其他割边形成一个环，而能继续进行缩点。
有割点的图不一定有割边，如：3是割点，分别与(1,2)和(4,5)形成两个无割点的块有割边的图也不定有割点,如：w(1,2)为割边，有向图强连通分量：有向图中任意两点相互可达的连通子图，其实也相当于无向图中的缩点二、算法无向图借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。
dfn[i]表示DFS过程中到达点i的时间，low[i]表示能通过其他边回到其祖先的最早时间。
low[i]=min(low[i],dfn[son[i]])设 v,u之间有边w(v,u)，从v->u：如果low[u]>=dfn[v],说明v的儿子u不能通过其他边到达v的祖先，此时如果拿掉v,则必定把v的祖先和v的儿子u，及它的子孙分开，于是v便是一个割点，v和它的子孙形成一个块。
如果low[u]>dfn[v]时，则说明u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果v,u之间有两条无向边，需要仍视为割边的话，则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去，从而第二条无向重边不会被遍历而导致low[u]==dfn[v] ,而在另外一些问题中，比如电线连接两台设备A,B 如果它们之间有两根电线，则应该视为是双连通的，因为任何一条电线出问题都不会破坏A和B之间的连通性，这个时候，我们可以用一个used[]数组标记边的id,DFS时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id号，在开始遍历v->u前检查它的id是否在上一次u->v 时被标记，这样如果两点之间有多条边时，每次遍历都只标记其中一条，还可以通过其他边回去，形成第二条新的路求割点的时候，维护一个栈st 每遍历到一个顶点v则把它放进去，对它的子孙u如果dfn[u]为0，则表示还没有遍历到则先DFS(u),之后再判断low[u]和dfn[v]，如果low[u]>=dfn[v],则把栈中从栈顶到v这一系列元素弹出，这些点与v 形成一个块，如果u的子孙x也是一个割点，这样做会不会错把它们和v，u放在一起形成一个块呢，这种情况是不会发生的，如果发现x是一个割点，则DFS 到x那一步后栈早就把属于x的子孙弹出来了，而只剩下v,u的子孙，它们之间不存在割点，否则在回溯到v之前也早就提前出栈了！画一个图照着代码模拟一下可以方便理解。
图的割点、桥与双连通分支[点连通度与边连通度]在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。
一个图的点连通度的定义为，最小割点集合中的顶点数。
类似的，如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。
一个图的边连通度的定义为，最小割边集合中的边数。
注：以上定义的意思是，即有可能删除两个或两个以上点的时候才能形成多个连通块！[双连通图、割点与桥]如果一个无向连通图的点连通度大于1，则称该图是点双连通的(point biconnected)，简称双连通或重连通。
一个图有割点，当且仅当这个图的点连通度为1，则割点集合的唯一元素被称为割点(cut point)，又叫关节点(articulation point)。
如果一个无向连通图的边连通度大于1，则称该图是边双连通的(edge biconnected)，简称双连通或重连通。
一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥(bridge)，又叫关节边(articulation edge)。
可以看出，点双连通与边双连通都可以简称为双连通，它们之间是有着某种联系的，下文中提到的双连通，均既可指点双连通，又可指边双连通。
[双连通分支]在图G的所有子图G’中，如果G’是双连通的，则称G’为双连通子图。
如果一个双连通子图G’它不是任何一个双连通子图的真子集，则G’为极大双连通子图。
双连通分支(biconnected component)，或重连通分支，就是图的极大双连通子图。
特殊的，点双连通分支又叫做块。
[求割点与桥]该算法是R.Tarjan发明的。
对图深度优先搜索，定义DFS(u)为u在搜索树（以下简称为树）中被遍历到的次序号。
定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。
一棵生成树的基本回路系统1.引言1.1 概述在计算机科学领域，生成树和回路系统是图论中的两个重要概念。
生成树是一个无向图的子图，它包含了原图的所有顶点，并且是一个连通图，即任意两个顶点之间都存在唯一的路径。
回路系统是图中由一些边和顶点构成的闭合路径的集合，每个闭合路径中的顶点和边都具有特定的关联性。
生成树和回路系统在实际问题的建模和求解中发挥着重要作用。
生成树可以用来描述一些优化问题，例如最小生成树问题，该问题的解决方法可以用来确定一个连通图的子图，使得这个子图的所有边的权重之和最小。
回路系统则常常出现在电路分析和网络规划中，用于描述电路中的闭合路径和网络中的环路。
本文将着重讨论生成树和回路系统的基本概念、定义和特性，探究它们之间的关系，并深入探讨它们在实际应用中的意义和应用领域。
接下来的章节将依次介绍生成树的基本概念和回路系统的定义与特性，以及它们在图论和实际问题中的应用。
通过对这些内容的研究和探讨，读者将能够更好地理解生成树和回路系统的内涵，进而应用于更广泛的领域中。
总之，生成树和回路系统作为图论中的核心概念，对于解决实际问题和优化分析具有重要意义。
本文将通过深入探讨它们的基本概念和特性，帮助读者更好地理解和应用这些概念，并展示它们在不同领域中的广泛应用。
文章结构部分的内容应该包括对整篇文章的组织和章节安排的介绍。
在本篇文章中，我们将按照以下结构来组织内容：1. 引言1.1 概述1.2 文章结构1.3 目的2. 正文2.1 生成树的基本概念2.2 回路系统的定义和特性3. 结论3.1 生成树和回路系统的关系3.2 应用领域和意义在引言部分，我们将首先对整篇文章进行一个简要的概述，介绍生成树和回路系统的基本概念，并明确文章的目的。
接下来，在正文部分，我们将详细讨论生成树的基本概念，包括什么是生成树以及它的特性。
然后，我们将介绍回路系统的定义和特性，探讨回路系统在图论中的重要性以及和生成树的关系。
第二章 图的连通性在第一章中已经定义连通图是任二顶点间都有路相连的图。
对于连通图，其连通的程度也有高有低。
例如，下列三个图都是连通图。
对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。
本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。
通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。
§2.1 割点和割边定义2.1.1 设)(G V v ∈，如果)()(G w v G w >−，则称v 为G 的一个割点。
（注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。
例如，下图中u , v 两点是其割点。
定理2.1.1 如果点v 是简单图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得][1E G 和][2E G 恰好有一个公共顶点v 。
证明留作习题。
推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G −不连通。
定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。
证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。
若0)(=v d ，则1K T ≅，显然v 不是割点。
若1)(=v d ，则v T −是有1)(−−v T ν条边的无圈图，故是树。
从而)(1)(T w v T w ==−。
因此v 不是割点。
以上均与条件矛盾。
充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。
路uvw 是T 中一条),(w u 路。
因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>−。
