一些特殊图的最大匹配的强迫数

发布时间：2021-03-31 03:26

　　设M是图G的一个最大匹配,S是M的一个子集.如果S除了被M包含而不被图G的其他最大匹配所包含,那么称S是M的一个强迫集.M的最小强迫集所包含的边数称作M的强迫数,记为f_M（G,M）.图G的所有最大匹配的强迫数的最小值称为图G的最小强迫数,记作f_M（G）.本文给出了一些特殊图类的最大匹配的强迫数的确切值. 

【文章来源】：厦门大学学报(自然科学版). 2020,59(06)北大核心CSCD

【文章页数】：5 页

【部分图文】：

P2n-1

图2 P2n-1容易得出图P2n-1恰好有n个最大匹配，故m(P2n-1)=n．图P2n-1中标号为奇数的每个点都分别对应一个不饱和该点的最大匹配，按照图P2n-1中不被某个最大匹配所饱和的点，给图P2n-1中的所有最大匹配进行标号，且分别用Mk(k=1,3，…，2n-1）来表示．

Km,n


本文编号：3110693