【摘要】：眾所周知,對集(或匹配)是圖論研究中的重要課題,不但具有理論意義,而且還有許多重要應(yīng)用價值.本文研究圖的對集問題以及相關(guān)性質(zhì)和算法.首先,運用反圈法和對稱差,不斷發(fā)現(xiàn)當前對集的可擴交錯路,直至找到最大對集.在此算法基礎(chǔ)上,導(dǎo)出了若干關(guān)于二部圖的相關(guān)組合結(jié)構(gòu)的結(jié)論(例如,Hall定理,Konig定理,邊染色定理等)。其次,經(jīng)過修改的上述算法,導(dǎo)出了著名的Edmond開花算法,運用證明中的反圈結(jié)構(gòu)性質(zhì)導(dǎo)出了一般圖的若干經(jīng)典結(jié)果(例如,Tutte的1-因子定理,Berge關(guān)于最大對集邊數(shù)計算公式等)。最后,給出上述算法的實際應(yīng)用。
[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

【相似文獻】

相關(guān)期刊論文 前4條

1 林毓材,顧震宇,陳玉華;組合星圖的拓撲結(jié)構(gòu)研究[J];云南師范大學學報(自然科學版);1998年02期

2 陳學剛,邢化明;圖的因子控制[J];山東科技大學學報(自然科學版);2004年03期

3 陳賜平;具有給定性質(zhì)的f-星因子[J];數(shù)學物理學報;1991年01期

4 ;[J];;年期

相關(guān)碩士學位論文 前1條

1 謝博耶夫;匈牙利算法及其推廣[D];華東師范大學;2016年

，

本文編號：2200747