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

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

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

【部分圖文】：

P2n-1

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

Km,n


本文編號：3110693