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

【相似文獻(xiàn)】

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

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

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

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

4 ;[J];;年期

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

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

，

本文編號：2200747