关于图的最大匹配问题的若干结果

来源 :郑州大学 | 被引量 : 0次 | 上传用户:ahaqwjtyl
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
The study on the maximum matchings (as well as perfect matchings) of a graph plays a central role in matching theory. In addition to the algorithnis of finding maximum matchings, the structural properties of all maximum matchings are significant in theory or application aspect. Roughly speaking, the properties we are concerned in this thesis are mainly as follows:1.How many maximum matchings are there in a graph?2.How are they transformed from each other?3.How are they growing from smaller matchings?In other words, we shall concentrate ourselves on the enumeration, the transformation graph and the extendability of maximum matchings. The organization of the thesis is as follows.In the first chapter, we list some terminologies, notations and introduce some topics about matching theory. In the second chapter, some results about the number of maximum matchings are presented. In the third chapter, the maximum matching graph of a graph is characterized. In the fourth chapter, we give degree conditions of induced matchingextendable graphs and conditions of a matching and a maximum matching being an induced one, respectively, and obtain some results about matching extendability.Number of Maximum MatchingsThe research on the number of perfect matchings can be found in many articles [11-14]. But not many results about the number of maximum matchings are known( even in bipartite graphs). In this part, some1results about this topic are presented. Firstly, We give some good lower bounds of the number.Theorem 1. Let G = (A, B) be a connected bipartite graph with positive surplus( as viewed from A). Then G has at least IE(G)I + (jAj ?1) * (def(G) ?2) maximum matchings.Theorem 2. Let G = (A, B) be a bipartite graph with positive surplus( as viewed from A), deficiency 1 and minimum degree at least 2. Then G contains at least 2jE(G)j ?21B1 near-perfect matchings.Theorem 3. Let G be a factor-critical graph. Then G has at least IE(G)I ?c)~near-perfect matchings, where c is the number of utverticesof C.~?bLocksThe enumeration problems for maximum matchings on some special graphs are solved.Theorem 4. Let C = (A, B) is a bipartite graph with positive surplus( as viewed from A) and deficiency 1. Then the following are equivalent:(i)Every vertex of A has degree 2;(ii)G is a tree;(iii) Every vertex of A is a barrier of G;(iv) C kas exactly IAI + 1 near-perfect matchings;(v)C ?v has a unique perfect matching for any vertex v C B.Theorem 5. Let C = (A, B) be a bipartite graph with positive surplus( as viewed from A), deficiency 1 and minimum degree 1. Then G has exactly ~E(G)j ?IAI + 1 near-perfect matchings if and only if there exists a vertex in NG(u) with degree 1 for any vertex u in A with degree at least 3.Theorem 6. Let G = (A, B) be a bipartite graph with positive surplus( as viewed from A), deficiency 1 and dG(v) = 2 for each vertex v in B. Then G has exactly 2jBI + 2m near-perfect matchings, where m is the number of cut vertices in B.Theorem 7. Let C be a 2-connected factor-critical graph. Then2G has precisely IE(G) near-perfect matchings if and only if there existsan ear decomposition of G starting with a nice odd cycle C; that is,G = C + P1 + ... ?Pk satisfying that P~ is open and two ends of P1 areconnected in G~1 by a pending path with length 2 of G for 1 <i < kwhereGo=CandG1=C盤i?..盤iforl<i<k.Theorem 8. Let G be a factor-critical graph. Then C has precisely IE(G)I ?c~iear-perfect matchings if and only if there exists an-4-Iear decomposition of C starting with a nice odd cycle C; that is, C =C + P1 + ... + Pk satisfying that two ends of P~ are connected in G~.1 by a pending path with length 2 of C for any open ear P,, where c is the nuniberof~r~j~ic~jofGandG1 = C+P1+...盤1,wherel <i< k.Maximum Matching GraphIn articles [25-27], authors defined the maximum matching graph as follows. The
其他文献
2018年,在水利部的坚强领导下,太湖流域管理局坚持以习近平新时代中国特色社会主义思想为指导,积极践行“节水优先、空间均衡、系统治理、两手发力”新时代治水方针,扎实推进
庭前会议的制度设计目的在于优化诉讼资源配置、解决程序性争端、整理案件争点。目前该制度存在启动方式不明确、被告人缺乏程序参与权、程序的效力未定等问题,并未充分实现
可持续发展已成为人们的共识,并成为世界各国的最优战略抉择和指导思想.区别于传统的GDP、GNP发展模式的一种新的可持续发展的经济模式,可持续发展的国民经济核算体系应运而
近年来,随着国民经济的快速发展,我国的宏观经济系统已经进入了混沌状态。经济系统中存在的混沌现象导致宏观经济运行具有不确定性,进一步加大了政府对经济宏观调控的难度。本文
相对于Engle-Granger两步法与Johansen方法,DOLS方法在小样本、联立性偏误、包容不同单整阶数等方面具有优越性。而拓展的弹性价格货币模型增加了汇率失调计算的理论成分。基
在我国,改革开放以前由于实行计划经济体制,货币流通速度比较稳定,中国人民银行对货币投放曾总结出1:8的经验数据,即如果现金流量与社会商品零售总额保持1:8的比例,那么货币流通就是