設(shè)M是圖G的一個(gè)最大匹配,S是M的一個(gè)子集.如果S除了被M包含而不被圖G的其他最大匹配所包含,那么稱S是M的一個(gè)強(qiáng)迫集.M的最小強(qiáng)迫集所包含的邊數(shù)稱作M的強(qiáng)迫數(shù),記為f_M（G,M）.圖G的所有最大匹配的強(qiáng)迫數(shù)的最小值稱為圖G的最小強(qiáng)迫數(shù),記作f_M（G）.本文給出了一些特殊圖類的最大匹配的強(qiáng)迫數(shù)的確切值. 

【文章來源】：廈門大學(xué)學(xué)報(bào)(自然科學(xué)版). 2020,59(06)北大核心CSCD

【文章頁數(shù)】：5 頁

【部分圖文】：

P2n-1

圖2 P2n-1容易得出圖P2n-1恰好有n個(gè)最大匹配，故m(P2n-1)=n．圖P2n-1中標(biāo)號為奇數(shù)的每個(gè)點(diǎn)都分別對應(yīng)一個(gè)不飽和該點(diǎn)的最大匹配，按照圖P2n-1中不被某個(gè)最大匹配所飽和的點(diǎn)，給圖P2n-1中的所有最大匹配進(jìn)行標(biāo)號，且分別用Mk(k=1,3，…，2n-1）來表示．

Km,n


本文編號：3110693