图的最大匹配个数的下界  

The Lower Bound on the Number of Maximum Matchings of a Graph

作　　者：翟绍辉 郭利涛 郑艺容 庄蔚 ZHAI Shaohui;GUO Litao;ZHENG Yirong;ZHUANG Wei(School of Applied Mathematics,Xiamen University of Technlogy,Xiamen 361024,China)

机构地区：[1]厦门理工学院应用数学学院,福建厦门361024

出　　处：《厦门大学学报（自然科学版）》2018年第5期680-683,共4页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金(11301440);福建省自然科学基金(2015J05017)

摘　　要：设G是一个具有n个顶点且最大匹配为k-匹配的连通图,这里n≥2k+1.证明了G至少有n-2k+1个互不相同的最大匹配,并且刻画了恰好具有n-2k+1个最大匹配的图.Let G be a connected graph of order n and let k be the size of maximum matchings in G,where n≥2k+1.In this paper,we present that G contains at least n-2k+1 distinct maximum matchings.In addition,we characterize graphs that possess exactly n-2k+1 distinct maximum matchings.

关 键 词：最大匹配 因子临界图 Gallai-Edmonds结构定理 

分 类 号：O157.5[理学—数学]