下载文档原格式
离散数学图的连通性判定方法介绍离散数学是一门研究离散结构以及这些结构中的对象、性质和关系的学科。
其中，图论是离散数学中的一个重要分支，主要研究图的性质和关系。
图是由节点和边组成的结构，可以用于表示各种实际问题以及计算机科学中的数据结构。
在图的研究中，连通性是一个重要的概念，它描述了图中节点之间是否存在路径相连。
在实际应用中，判断图的连通性是一个常见的问题。
下面将介绍几种常用的图的连通性判定方法。
1. 深度优先搜索（DFS）深度优先搜索是一种常用的图遍历算法，它通过栈来实现。
该算法从图的某个节点开始，首先访问该节点并将其标记为已访问，然后递归地访问它的邻居节点，直到所有可达的节点都被访问过。
如果在搜索过程中访问了图中的所有节点，则图是连通的。
否则，图是不连通的。
2. 广度优先搜索（BFS）广度优先搜索也是一种常用的图遍历算法，它通过队列来实现。
与深度优先搜索不同的是，广度优先搜索首先访问图中的某个节点，并将其标记为已访问。
然后访问该节点的所有邻居节点，并将未访问的邻居节点加入队列。
接下来，依次从队列中取出节点并访问其邻居节点，直到队列为空。
如果在搜索过程中访问了图中的所有节点，则图是连通的。
否则，图是不连通的。
3. 并查集并查集是一种数据结构，用于管理元素之间的动态连通性。
在图的连通性判定中，可以使用并查集来判断图中的节点是否连通。
首先，将每个节点都初始化为一个独立的集合。
然后，遍历图中的所有边，如果两个节点之间存在边，则将它们所在的集合合并为一个集合。
最后，判断图中是否只存在一个集合，如果是，则图是连通的。
否则，图是不连通的。
4. 最小生成树最小生成树是一种保留了图连通性的树结构。
在连通性判定中，可以通过构建最小生成树来判断图的连通性。
首先，选择一个节点作为起始节点。
然后，从所有与当前树相连的边中选择权值最小的边，并将连接的节点加入树中。
重复该过程，直到树中包含了图中的所有节点。
如果最后构建的树包含图中的所有节点，则图是连通的。
三、连通性3.1 连通性和Whitmey定理定义V’真包含于V(G)，G[V(G)-V’]不连通，而G是连通图，则称V’是G的顶剖分集。
最小顶剖分集中顶的个数，记成κ(G)，叫做G的连通度；规定κ(Kv)=υ-1；κ(不连通图)= κ(平凡图)=0。
由一个顶组成的顶剖分集叫割顶。
没有割顶的图叫做块，G中的成块的极大子图叫做G的块。
定义E’包含于E(G)，G为连通图，而G-E’(从G中删除E’中的边)不连通，则称E’为G的边剖分集，若G中已无边剖分集E″，使得|E″|<|E’|,则称|E’|为G的边连通度，记成κ’(G)。
|E’|=1时，E’中的边叫做桥。
规定κ’(不连通图)=0，κ’(Kv)= υ-1。
定义κ(G)>=k时，G叫做k连通图；κ’(G)>=k时，G称为k边连通图。
k连通图，当k>1时，也是k-1连通图。
k边连通图，当k>1时，也是k-1边连通图。
上面就是顶连通与边连通的概念，好象不指明的就是指顶连通了。
定理1 κ(G)=<κ’(G)=<δ(可以复习一下第一章的1.2：δ=min{d(v i)})证：设d(v)=δ，则删除与v边关联的δ条边后，G变不连通图，所以这δ条边形成一个边剖分集，故最小边剖分集边数不超过δ，即κ’(G)=<δ。
下证κ=<κ’。
分情形讨论之。
若G中无桥，则有κ’>=2条边，移去它们之后，G变成不连通图。
于是删除这κ’条中的κ’-1条后，G变成有桥的图。
设此桥为e=uv，我们对于上述κ’-1条删去的每条边上，选取一个端点，删除这些(不超过κ’-1个)端点，若G变得不边能，则κ=<κ’-1；若仍连通，则再删去u或v，即可使G变得不连通，于是κ=<κ’。
证毕。
这个定理很好理解，图论中的一些定理常以这种“友好”的面目出现。
下面就是Whitmey定理定理2(Whitney,1932) υ>=3的图是2连通图的充要条件是任二顶共圈(在一个圈上)。
图像连通域的概念图像连通域是指图像中一组相邻的像素点，它们具有相同的属性或特征，且通过相邻像素之间的连接关系形成一个连通区域。
每个像素点可以看作是一个图像中一个最小的连通域，而多个连通域的集合则构成了整个图像。
图像连通域的概念对于图像处理和分析非常重要，可以用于目标检测、图像分割、特征提取等领域。
在实际应用中，常常需要识别和提取图像中的不同连通域，以便进一步进行后续处理。
在图像中，连通域可以是任意形状的区域，这取决于图像中像素点之间的连接关系。
而像素点之间的连接关系通常是通过像素点的空间位置和像素值的相似度来定义的。
在图像处理中，常常使用的连接关系有4邻接和8邻接。
4邻接表示一个像素点的上、下、左、右四个邻域像素，而8邻接则表示上、下、左、右以及对角线的八个邻域像素。
这两种邻接方式可根据具体应用需求选择。
连通域分析的基本原理是通过扫描整个图像，从每一个像素点开始，查找满足连接条件的相邻像素点，并将它们组成一个连通域。
常使用的算法有基于种子点的扫描算法和基于区域增长算法。
基于种子点的扫描算法从图像中选择一个种子点开始，通过不断扩展种子点的相邻像素，并标记已访问过的像素点，以便于后续处理。
该算法适用于具有清晰边界和简单连通域形状的图像。
基于区域增长的算法则通过像素值的相似性来判断像素点是否属于同一个连通域。
该算法从一个种子点开始，逐步增长满足相似性条件的像素点，直到达到预设的停止条件。
该算法适用于具有复杂连通域形状和灰度值变化较大的图像。
除了基本的连通域分析算法，还有一些改进和扩展的算法可以应用于特定的图像处理任务。
例如，基于区域的分割算法、基于轮廓的形状分析算法等。
这些算法利用图像连通域的特性进行目标检测、分类和识别等任务。
总的来说，图像连通域是指图像中一组相邻的像素点，通过连接关系形成的连通区域。
连通域分析是图像处理和分析中常用的技术，可用于目标检测、图像分割、特征提取等领域。
不同的连通域分析算法可以根据具体应用需求选择，以实现对图像中连通域的识别和提取。
三、连通性3.1 连通性和Whitmey定理定义V’真包含于V(G)，G[V(G)-V’]不连通，而G是连通图，则称V’是G的顶剖分集。
最小顶剖分集中顶的个数，记成κ(G)，叫做G的连通度；规定κ(Kv)=υ-1；κ(不连通图)= κ(平凡图)=0。
由一个顶组成的顶剖分集叫割顶。
没有割顶的图叫做块，G中的成块的极大子图叫做G的块。
定义E’包含于E(G)，G为连通图，而G-E’(从G中删除E’中的边)不连通，则称E’为G的边剖分集，若G中已无边剖分集E″，使得|E″|<|E’|,则称|E’|为G的边连通度，记成κ’(G)。
|E’|=1时，E’中的边叫做桥。
规定κ’(不连通图)=0，κ’(Kv)= υ-1。
定义κ(G)>=k时，G叫做k连通图；κ’(G)>=k时，G称为k边连通图。
k连通图，当k>1时，也是k-1连通图。
k边连通图，当k>1时，也是k-1边连通图。
上面就是顶连通与边连通的概念，好象不指明的就是指顶连通了。
定理1 κ(G)=<κ’(G)=<δ(可以复习一下第一章的1.2：δ=min{d(v i)})证：设d(v)=δ，则删除与v边关联的δ条边后，G变不连通图，所以这δ条边形成一个边剖分集，故最小边剖分集边数不超过δ，即κ’(G)=<δ。
下证κ=<κ’。
分情形讨论之。
若G中无桥，则有κ’>=2条边，移去它们之后，G变成不连通图。
于是删除这κ’条中的κ’-1条后，G变成有桥的图。
设此桥为e=uv，我们对于上述κ’-1条删去的每条边上，选取一个端点，删除这些(不超过κ’-1个)端点，若G变得不边能，则κ=<κ’-1；若仍连通，则再删去u或v，即可使G变得不连通，于是κ=<κ’。
证毕。
这个定理很好理解，图论中的一些定理常以这种“友好”的面目出现。
下面就是Whitmey定理定理2(Whitney,1932) υ>=3的图是2连通图的充要条件是任二顶共圈(在一个圈上)。
证：若任二顶共圈，任删除一个顶w后，得图G-w。
任取两顶u,v∈V(G-w)，u,v在G中共存于圈C上，若w不在C上，则G-w中仍有圈C，即u与v在G-w 中仍连通；若w在G中时在C上，在G-w中u与v在轨C-w上，故u与v仍连通。
由u与v之任意性，G-w是连通图，故κ(G)>=2，即G是2连通图。
反之，若G是2连通图，υ>=3,任取u,v∈V(G)，用对d(u,v)的归纳法证明u 与v之间有两条无公共内顶的轨当d(u,v)=1是时，因κ=<κ’=<δ，故κ’>=2，uv边不是桥，G-uv仍连通，于是G-uv中存在从u到v的轨P1(u,v),这样从u到v有两条无公共内顶的轨P1(u,v)与边uv。
假设d(u,v)<k时(k>=2),结论已成立，考虑d(u,v)=k的情形。
令P0(u,v)之长为k,w是P0(u,v)上与v相邻的顶，则d(u,w)=k-1，由归纳法假设，在u,w之间有两条无公共内顶P与Q，因G是2连通较长，故G-w仍连通。
在G-w中存在轨P’(u,v)<>P0(u,v)，令x是P∪Q上P’的最后一个顶。
因u∈P∪Q，故x存在(可能x=u)。
不妨设x∈V(P)，则G有两个u,v之间无公共内顶的轨：一个是P上从u到x段并在P’上从x到v段；一个是Q+wv。
证毕。
图论的定理证明，没有其他数学的那么多推导，那么多的公式，符号也是有限的几个，看多了就明白了。
概念清晰还是很重要，很多东西是概念性的。
还有就是构造了，照题能构造出的相应的图有时就迎而解了。
就是打字时中英文切换麻烦。
3.2 割顶、桥、块割顶、桥、块都是一个图的关键部位了。
本节给出三个定理来阐述这三个概念，好象少了点，不过这本书的东西有些地方很语焉不详的，而且有些东西到处穿插，并且有很强的理论性，很少涉及实践中的问题。
看起来比较的累人。
定理3 v是连通图的一个顶点，则下可述命题等价：(1)v 是割顶(2)存在与v不同的两个顶u,w，使得v在每一条由u到w的轨上(3)存在V-{v}的一个划分V-{v}=U∪W，U∩W=φ，使得对任意的u∈U,w∈W,v在每一条由u到w的轨上。
定理4 x是G的一边，G是连通图，则下述命题等价：(1)x是G的桥。
(2)x不在G的任一圈上。
(3)存在顶u,v∈V(G),使得x在每一个从u到v的轨上。
(4)存在V(G)的划分U与W，使得任二顶u,w, u∈U,w∈W时，x在每条从u到v的轨上。
上面的都没什么可证的，就是轨、连通片、割顶、桥等概念翻来覆去的用就是了。
定理5 G连通，υ>=3,则下列命题等价：(1)G是块。
(2)G的任二顶共圈。
(3)G的任一顶与任一边共圈(4)G的任二边共圈(5)任给G的二顶及一边，存在连接此二顶含此边之轨(6)对G的三个不同的顶，存在一轨，连接其中两个顶，含第三个顶(7)对G的三个不同的顶，存在一轨，连接其中两个顶，不含第三个顶。
(本也没什么可证的了，但就这样结束了也太快了，这个证一下)证：(1)>>(2)，(2)>>(1)见定理2(2)>>(3) 只考虑u为G的任给一个顶，vu是G中任给定的一条边，且u<>v,u<>w的情形。
设C是含u与v的圈，若w在C上，则C上含u的轨P(v,w)与边vw形成一个圈，它含u及边vw。
若w不在C上，因v不是割顶，由定理3，存在不含v的轨P(w,u)。
令u’是P(w,u)与C从w沿P(w,u)看来的第一个公共顶，则由边vw,P(w,u)上w到u’段，以及C上含u的轨P’(u’,v)并成一个圈，此圈满足(3)的要求。
(3)>>(4)与(2)>>(3)类似证明。
(4)>>(5) 已知任二边共圈，设u,v是G上任给定的两个顶，x是任给定的一条边，只考虑x与u,v皆不相关联的情形。
由任二边共圈显然有任二顶共圈，于是由于(2)>>(3)知u与x共圈，设此圈C1；同理v与x共圈，设此圈是C2；若v∈C1或u∈C2,则(5)成立；若u不属于C2，且v不属于C1，则如下构作含x之轨P(u,v):从u出发沿C1到达C1与C2上第一个公共顶w,再从w出发沿C2含x的部分到达v。
(5)>>(6) 设u,v,w是G的三个顶，且与w相关联的一条边是x,由(5)存在轨P(u,v)，x在P(u,v)上，于是w在P(u,v)上。
(6)>>(7) u,v,w∈V(G),由(6)，存在轨P(u,w)，P(u,w)含顶v,则P(u,w)的从u 到v的一段不含w。
(7)>>(1) 由(7)，对任给定的二顶u与v,不存在这样的顶，它在从u到v的每一轨上，由定理3，G无割顶，故G是块。
证毕。
讲了这么多，下节才涉及到实践中的问题。
下节讲可靠通讯网的构作。
不过下节又是本章的最后一节了。
3.3 可靠通讯网的构作我们要构作一个有线通讯网，使得敌人炸坏我几通讯站后，其余的通讯站仍然可彼此通话。
显然，有两个要求是必要的：一是不怕被敌人炸坏站的数目要多，一是整个造价要小。
这个实际问题的数学艺术模型如下：G是加权连通图，k是给定的自然数，求G的有最小权的k连通生成子图。
当k=1时，它就是用Kruskal算法求得的生成树；当k>1时，是尚未解决的难解问题之一。
哦，原来k>1时是没解决的难题，自己以前也想过这方面的东西，只是想了半天也想不出个所以然，原来是个大难题呀。
当G=Kυ，每边权皆为1时，Harary于1962年解决了这一问题。
下面介绍Harary的工作。
令f(m,n)表示n个顶的m连通图当中边数的最小值，m<n。
由Σd(v)=2e，κ=<κ’=<δ，f(m,n)>={mn/2}Harary实际上构作出一个n顶的m连通图，它的边数恰为{mn/2}条，且f(m,n)={mn/2}。
此图记成H(m,n) 。
(1)m是偶数，m=2r。
H(2r,n)以{0,1,2,…,n-1}为顶集合。
当i-r=<j=<i+r时，在顶点i与j之间连一边，这里的加法在mod n意义下进行。
(2)m是奇数，m=2r+1,n是奇数。
先构作H(2r,n),然后对1=<i=<n/2的i,在i与i+n/2间加上一条边得H(2r+1,n)。
(3)m是奇数，m=2r+1,n是奇数。
先构作H(2r,n),然后在顶点0与(n-1)/2,0与(n+1)/2之间加上边，在顶i与i+(n+1)/2间加上边，其中1=<i=<(n-1)/2，则得到H(2r+1,n)。
无法把图画上来，H(6,8)、H(5,8)、H(5,9)看一下图就明白这个构作的方法了。
下面证上面的构作出来的东西是符合要求的。
定理6 H(m,n)是m连通图，且边数最少证：m=2r时，我们来证明H(2r,n)，设有少于2r个顶组成的顶剖分集。
若V'是一个顶剖分集，且|V'|<2r，又设i与j两个顶分别属于H(2r,n)-V'的不同连通片，令S={i,i+1,...,j-1,j},T={j,j+1,...,i-1,i},其中加法在mod n下执行。
因为|V'|<2r，不失一般性，设|V'∩S|<r，则显然存在S-V'中的序列，从i如至j终，使得序列中连续二顶之差的绝对值最大是γ。
但这样的序列中相邻顶之间由(1)知存在边，即在H(2r,n)-V'中有轨P(i,j),与i,j分居于H(2r,n)-V'的两年连通片中相矛盾，故H(2r,n)是2r连通的。
相似地可以证明m=2r+1时，H(2r+1,n)是2r+1连通的。
由于f(m,n)>={mn/2}, ε(H(m,n))={mn/2},而H(m,n)是n顶m连通图，故有f(m,n)=<{mn/2},从而得ε(H(m,n))=f(m,n)={mn/2}。
证毕。
由于κ=<κ'，故H(m,n)也是m连通图，若用g(m,n)表示n个顶m边连通图中最少边数，则对1<m<n,g(m,n)={mn/2}。
就这样第三章也结束了，理论讲了一大堆一、通论1．1 图论的内容与历史回顾一上来总要先回顾一下历史，让人了解一下这个学科的来龙去脉，见怪不怪了。
柯尼斯堡七桥问题这个实在是太有名了，图论从这开始的，从很久以前就知道了。
欧拉这个人真的是厉害，在数学的各个领域都留有他的足迹。
噢，从欧拉之后停滞了好长一段时间(再次可见欧拉的水平，对他是佩服得五体投地呀，不服不行)，直到二百年后，1936年匈牙利的Konig(书上的名字打不上来呀，字母怪怪的，随便用其他字母替了)发表了《有限图与无限图理论》这第一本图论的专著，图论才获得了长足的发展，成长了数学中的一门独立的学科。
