免费下载
网站简介

找论文变得更简单!

帮找论文

当前位置:

重点论文网    理科论文    信息与计算科学论文    树的最大匹配简易算法
创建时间:09-25

树的最大匹配简易算法


1、    研究的意义,同类研究工作国内外现状、存在问题(列出主要参考文献)
目前最大匹配的算法主要是1965年Edmonds 。而树和图的最大匹配一般算起来比较困难。而匹配在日常生活及生产管理中有着普遍意义,而传统的方法比较复杂和计算困难。针对最大匹配问题的解决方法主要是匈牙利算法。它是对未饱各的点生长一个M_交错树,逐步扩大匹配。最终达到求出最大匹配的目的。通过不断的寻找增广路来解决匹配。这种方法均不可避免的要对已经计算过的点(或线)在不同程度上重新进行计算。这样当图和树的点数相当大时,其计算量也是很大的。而目前在研究图和树的最大匹配问题上,大多采用找增广路径的方法。计算相对复杂。争对这些问题,论文给出了两种不同的算法。与其它经典算法的比较,这两种算法的复杂度明显要优于经典算法。

2、研究目标、内容和拟解决的关键问题(根据任务要求进一步具体化)
本文对特殊图—树用图形去边方法和关联矩阵方法两种不同的方法解决求图和树的最大匹配问题,将使这类问题得以简化。算法没有重复计算。从而在计算量上比匈牙利算法大大降低。
图形去边法主要是从图和树的图形出发。通过不断去掉图和树上与某一边相关联的边,一步步简化图形,层层推进最终得到最大匹配。该算法在关键在于算法的证明。为了证明该算法的合理性,论文从树和图的邻接矩阵着手,论证最大匹配的数与邻接矩阵秩的关系,得出图和树的最大匹配所含线数目完全取决于图和树邻接矩阵的秩数。从而得到算法。
关联矩阵法则是从图形去边法中得到启示。运用树和图的上的边在关联矩阵上的表示。划去图和树上的相关联的线转到关联矩阵上就是的划去关联矩阵上的行和列。论文用数学归纳假设法论证了算法的合理性。
3、特色与创新之处
这两种算法的思路清晰简捷。利于操作。算法复杂度得到简化。
去边法从图形本身出法,直观的根据匹配的相关定义和性质划去相关联的边得到最大匹配。
关联矩阵法则是从去边法的启示中得出。利用关联矩阵的几何意义划去行和列表示的几何意义来求解最大匹配。并根据该算法给出了程序实现。

4、拟采取的研究方法、步骤、技术路线
(1)本论文通过对已有经典算法的研究,通过比较的方法,直观的比较论文中的算法和经典算法。
(2)从图和树的图形出发,直接根据匹配的定义和性质设计算法。
(4)利用数学归纳假设法证胆算法。
(4)在解决算法证明后,对算法进行了程序实现。
5、使用的主要仪器设备、试剂和药品
MATLAB
6、参考文献
[1] 耿素云 屈婉玲 张立昂 编著<<离散数学(第三版)>> 清华大学出版社出版
[2] 孙惠泉 编著 <<图论及其应用>> 科学出版社出版 
[3] 徐俊明  编著<<图论及其应用>>  中国科学技术大学出版社
[4] 李建湘 <<关于树图的秩与行列式的计算>>  湖南邵阳工专学报  1992年1月
[5]蔡永裕 周利仙  李世群 编著 《高等代数学习指导》
[6]杨洪  编著<<图论算法选编>> 中国铁道出版社出版  1988年
[7] Bernard Kolman ,Robert C。Busby <<离散数学结构(第五版翻译版)>> 高等教育出版社  
[8]Tmonas H.Cormen 著,潘金贵译<<算法导论>> 机械工业出版社出版

目   录
前言………………………………………………………….……….1
第一章 匹配的经典算法介绍………………………….…………..2 
第二章 基本概念及定义……………………………….…………………..3
第三章 树的最大匹配去边算法………………………….…….………..4
  3.1算法的相关定理及证明…………………………………………………..4
3.2 算法步骤…………………………………………….……………………6
3.3 算法的证明………………………….………………..………………….7
3.4 举例…………………………………………………..…………………..8
3.5算法总结…..…………………………………………..……….………11
第四章  树的最大匹配关联矩阵算法……………………………11
  4.1 算法描述………………………………………………………………12
  4.2 算法的证明……………………………………………………………13
  4.3 举例……………………………………………………..………………14
  4.4算法总结………………………………………..……………………..17
第五章 算法的程序实现………………………………….………………19
第六章 总结………………………………………………………………….20
参考文献………………………………………………………………………21
致谢………………………………………………………….…………………22      
 

前     言
目前最大匹配的算法主要是1965年Edmonds 。而树和图的最大匹配一般算起来比较困难。而匹配在日常生活及生产管理中有着普遍意义,而传统的方法比较复杂和计算困难。针对最大匹配问题的解决方法主要是匈牙利算法[3]。它是对未饱各的点生长一个M_交错树,逐步扩大匹配。最终达到求出最大匹配的目的。通过不断的寻找增广路来解决匹配。这种方法均不可避免的要对已经计算过的点(或线)在不同程度上重新进行计算。这样当图和树的点数相当大时,其计算量也是很大的。因此为了解决算法复杂度过大的不利。本文对特殊图—树用图形去边方法和关联矩阵方法两种不同的方法解决这类问题,将使这类问题得以简化。算法没有重复计算。从而在计算量上比匈牙利算法大大降低。图形去边方法直观且操作简单。而关联矩阵的方法简洁又便于计算机软件编程计算这类问题。
文献[2]、[3]介绍了一些基本的最大匹配算法,但停留在寻找增广路的理论知识的介绍层面上,而对图的图形以及它的关联矩阵在解题中的应用介绍很少,对如何结合图的图形及其对应的矩阵也没有进行详细地阐述与研究。但用树的最大匹配去边法和树的最大匹配关联矩阵算法的关键便在于对图的图形的研究和图的关联矩阵研究。通过删除相关联的边,一步步扩大图的匹配集进而求出它的最大匹配。
本文就是研究树的最大匹配的简易算法。本文分为六节,第一节为经典算法的介绍;第二节 相关定义的介绍。第三、树的最大匹配去边算法的相关定理以及算法的证明 。第四节树的最大匹配关联矩阵算法的相关定理以及算法的证明;在第五节算法的程序实现。第六章则是总结。论文旨在通过邻接矩阵的方法得到一种去边法求树的最大匹配的算法;并通过图与其关联矩阵的关系,利用树的关联矩阵寻找出树的最大匹配的关联矩阵算法这一个新算法。通过与传统算法的比较体现新算法的优越性。论文还通过参考文献[6][7][8]对树的最大匹配关联矩阵算法进行了程序设计工作。
 

第一章  匹配的经典算法介绍

经典算法中具有代表性的是Edmonds(1965年)算法也称为匈牙利算法。
匈牙利算法是以一个匹配M(可为空集)开始,用系统搜索M-可扩路的办法来增长当时的匹配M的边数。算法开始是及每次通过M-可扩路更新M后,都先检查X中是否有M-不饱和顶点,若没有,M就是所找到的最大匹配;不然令u为X中的M-不饱和顶点,处法用生长”以u为根的M-交错树”的办法来系统搜索以u为顶点的M-可扩路。在生长过程中,树中除u外都是M饱和的,且保持S\{u}与T在M下相匹配,因此恒有|S|-1=|T|。只当N(S)  T,即存在边xy使 也即存在一边从S”迈到”T外时,树才得以生长。生长到一个M-不饱和的顶点 时:找到一个M-可扩(u,y)-路P。这时匹配 M加1,并重新系统搜索M-可扩路。
匈牙利算法 :设偶图G=(X,Y,E)
步骤1.任给初始匹配M; 
步骤2.若X已饱和则结束,否则进行第3步; 
步骤3.在X中找到一个非饱和顶点 ,作  ← { },  ← Φ; 
步骤4.若T( ) =  则因为无法匹配而停止,否则任选一点y ∈T( )\ ; 
步骤5.若y已饱和则转6

最新论文

网站导航

热门论文