匈牙利算法及其推广
发布时间：2018-08-24 11:53
【摘要】：众所周知,对集(或匹配)是图论研究中的重要课题,不但具有理论意义,而且还有许多重要应用价值.本文研究图的对集问题以及相关性质和算法.首先,运用反圈法和对称差,不断发现当前对集的可扩交错路,直至找到最大对集.在此算法基础上,导出了若干关于二部图的相关组合结构的结论(例如,Hall定理,Konig定理,边染色定理等)。其次,经过修改的上述算法,导出了著名的Edmond开花算法,运用证明中的反圈结构性质导出了一般图的若干经典结果(例如,Tutte的1-因子定理,Berge关于最大对集边数计算公式等)。最后,给出上述算法的实际应用。
[Abstract]:As we all know, pair set (or matching) is an important subject in the study of graph theory, which not only has theoretical significance, but also has a lot of important application value. In this paper, we study the set problem of graphs and its related properties and algorithms. Firstly, by using the inverse cycle method and symmetry difference, the extensible interlaced paths of the current pair are continuously found until the maximum pair is found. On the basis of this algorithm, some conclusions on the related combinatorial structures of bipartite graphs (such as Hall theorem Konig theorem, edge coloring theorem, etc.) are derived. Secondly, the famous Edmond blooming algorithm is derived by the modified algorithm, and some classical results of the general graph are derived by using the properties of the anti-cycle structure in the proof (for example, the 1-factor theorem of Tutte and Berge's formula for calculating the maximum logarithmic number of edges, etc.). Finally, the practical application of the above algorithm is given.
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
本文编号：2200747
[Abstract]:As we all know, pair set (or matching) is an important subject in the study of graph theory, which not only has theoretical significance, but also has a lot of important application value. In this paper, we study the set problem of graphs and its related properties and algorithms. Firstly, by using the inverse cycle method and symmetry difference, the extensible interlaced paths of the current pair are continuously found until the maximum pair is found. On the basis of this algorithm, some conclusions on the related combinatorial structures of bipartite graphs (such as Hall theorem Konig theorem, edge coloring theorem, etc.) are derived. Secondly, the famous Edmond blooming algorithm is derived by the modified algorithm, and some classical results of the general graph are derived by using the properties of the anti-cycle structure in the proof (for example, the 1-factor theorem of Tutte and Berge's formula for calculating the maximum logarithmic number of edges, etc.). Finally, the practical application of the above algorithm is given.
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【相似文献】
相关期刊论文 前4条
1 林毓材,顾震宇,陈玉华;组合星图的拓扑结构研究[J];云南师范大学学报(自然科学版);1998年02期
2 陈学刚,邢化明;图的因子控制[J];山东科技大学学报(自然科学版);2004年03期
3 陈赐平;具有给定性质的f-星因子[J];数学物理学报;1991年01期
4 ;[J];;年期
相关硕士学位论文 前1条
1 谢博耶夫;匈牙利算法及其推广[D];华东师范大学;2016年
，本文编号：2200747
本文链接：https://www.wllwen.com/kejilunwen/yysx/2200747.html
