图论的算法与应用分析

研究园地图论的算法与应用分析杨迪(辽宁石化职业技术学院辽宁省 锦州市121001)摘要:图论中所产生的很多理论和概念都是既相互联系,也相互独立的。图论的算法作为解决一系列问题步骤的主要集合,在离散数学中占据着重要的地位。了解图论的理论和具体应用方法,深入研究图论算法和理论,最后举出图论理论和方法在应用中的具体例子。关键词:图论:算法与应用:分析中图分类号:TP18文献标识码:A文章编号: 1004-7344 2015)35- 0338-01从图论的性质上来讲，图论属于离散数学学科,所以，在学习图论中|突出问题和简化问题这是建立图论模型的重点,也是为了可以更加方便会涉及到很多离散数学的知识。图论作为数学的重要分支,广泛运用在|和深入探讨问 题的本质,最终求解目标是为了可以更好的优化问题。各领域中,比如:信息论、计算机技术、物理学等等领域中,对于在这些领比如，共有三根小棍子,起长度分别为7,9, 10,它们可拼接处的长度域内所存在的一些疑 难问题,利用图论都可以完美解决，因此,越来越多|为 7,9, 10, 11,12, 13, ....的木棍，其实从式子中看上去9就是答案，的数学家开始深度研究和探讨图论,希望可以利用图论解决更多的疑难但是怎样才能证明呢?这样, 我们可以考虑将拼接出来的术棍长度为x,根据可以考虑把能1简介图论的主要算法够拼出来的术棍长度x根据模7的结果分成3类(0, 1,2)对于x mod7=0,可以拼接出来，则14, .2....模7为0的数最终都可以实现拼接。1.1 阈值分割算法的应用目前，阈值分割算法被广泛运用基于区域的一种分割图像技术，它对于xmod7=I, 15能被拼出来,那么22,29, 3...都可以被拼接出来。是运用图像中需要提取的背景与目标之间的差异,将图像视作为具备不|来对于xmod7=2,16能被拼出来，那么23,30,7....都可以被拼接出同灰度等级的组合,选出一个最佳的阈值,最终确定出在图像中所存在也就是证明7是最后的答案。的像素点，是属于背景还是属于目标。在利用阙值分析法中，首先应该确从上述的证明中，我们将最终结果扩展一-下:定出图像灰度范围阙值,这个阈值用T表示，然后再将图像中所存在的我们假设n根术棍的长度分别为L,,L,假设L是最短的一根每一个像素值都可以与这个阈值相似。可以说,这两种不同类型的像素是属于”^般图像中两类区城，因此，根据具体的阀值最终达到分制区城术棍， 现在可以将能够拼出来的术棍长度依据模型l最终结果,可以分的主要目的。其中输出图像可以是B(.y),输入图像可以是F(.vy),那为成为 L.类(0, 1-1-.1),如果某类别中的 L结果是i,那么它们之间么共同的集合可以为s,存在这样的情况,显然此题无解。B(x.y)=) Pauy) >τ现在我们假设所有集合都有值:假设每一一个集合中最 小的元素为by,h**b,-1在利用这个方法中我们可以得出，确定出一个最佳的阅值是非常重怎样才能解答出题目中所要求的k?要的，但这也是分割阀值的难题所在。可考虑这样的数值:k'max(b,)-L,1≤L, (b=O,不考虑),作为最1.2最小支撑树聚类算法的应用短的术棍，因此:k>0Gahn是最早提出最小支撑树聚类算法的学者，他将每一一个像 素作(1):k'不是s中的元素:为一个具体的节点,按照部分空间和灰度之间的关系,计算最终权值,因(2)对每-一个L>k',假设L∈S,L+L,=max{b,}≥b,所以L≥h,-L但为割集了模糊边界和噪声，直接影响了最终的分裂效果，在通过改造之| lL=h, (mod )因此l>h.后,进一-步分析了模糊聚类的实现，如下为具体改造方法:在上述(1)和(2)两点中,我们可以得知k'绝对不是被拼接出来的术(1)在进行初始化过程中,将灰度相同的像素可划分为同--种类,其棍的最大值,其实k'+1才是我们所求的答案。他像素划分为另外种类,然后再根据像素灰度的不同,将原始图像再分最后一步求解b,.."h, - 1.实际上,每个可以被拼接出来的x,都应为儿种类型的子图,这就要求每一-个子图的像素灰度是相符的，在这样该从0开始,也是用所存在的小木棍进行拼接。这样可将集合编号作为的情况下，最多可以分为成255个子图，并且每一一个子图中包含着灰度顶点。 每一 一个 i(集合i),都可以连接出n条边，其长度分别为LL。其中长度为L的边。对于随意的一个数字，都可以拼接成为x (设(2)将各个连通域可作为具体的一类。xmodL,=P) 依据上述所讲的建图规则。得出如下结论:(3)对每一个子图都要进行标记连通域,这样就可以将原始图像分s,中的最小元素就是顶点0到顶点P的最短路径的实际长度。成若干个不同的连通域。所以,这个问题也完美解决了。(4)权重的具体计算。既需要计算连通域各边缘节点之间的权重,也3 结语应该加入具体节点和区域空间，也就是W=(1-μ) 0+μw' ,其μ∈[0,1]表总而言之，在建模过程中,应用图论模型原理,可以解决很多实际问示为空间:关系影响因子,其中图论算法的权值用0代表,空间区域近邻页。 在特定理论体系结构上,应用相应的元素，建立起最佳的模型,再根据关系中所得到的邻值用w代表,定义如下:自身的实际需要,展开必要的优化。无论是图论算法，还是图论理论，都具有其精妙之处。所以，应该深度研究图论模型原理,充分利用其规律。aw'(0(p,Z)=(N.xD(p,Z)1 ZNxD(,ZJ}(5)实现图像分割的效果,构造出最小支撑树。参考文献其节点与各个区域间的关系主要指:[u]姚朝灼.图论算法的可视化操作平台设计J.福州大学学报(自然科学Vρ∈G,区域zCG,如果节点ρ那么区域z之间所产生的距离可版) ,2006(01).[2]蔣建,孙蕊.图论模型的建立及转化方法[J]郑州航空工业管理学院学以定义成D(,Z)= (lp(p.p.)),则到节点ρ区域z间距离为D|报(社会科学版) " 20602)2收稿日期:2015-11-292在模型中图论的具体应用作者简介:杨迪(1980-中国煤化工士研究生,主要在解决图论问题过程中，通常都需要进行建模,所谓的建模也就是从事应用数学，及图论的MHCNMHG抽象和简化一些客观事物， 并且利用图来描述各事物之间的内在联系。大科技 3382015年12月