图的最大匹配个数的下界

作者：翟绍辉^*; 郭利涛; 郑艺容; 庄蔚

来源：厦门大学学报(自然科学版), 2018, 57(05): 680-683.

• 最大匹配
• 因子临界图
• Gallai-Edmonds结构定理

设G是一个具有n个顶点且最大匹配为k-匹配的连通图,这里n≥2k+1.证明了G至少有n-2k+1个互不相同的最大匹配,并且刻画了恰好具有n-2k+1个最大匹配的图.

• 单位
  数学学院; 厦门理工学院