覆蓋集

覆蓋集(covering set)數學的一個重要概念.這裏指一類節點子集.具體地説，圖的一個節點子集使該圖的每一條邊都與這個子集中一個節點關聯，稱這樣的節點子集為覆蓋集，也稱點覆蓋集，簡稱覆蓋.圖G的最小覆蓋，也稱最小點覆蓋，是指在圖的所有覆蓋中，節點數最少的覆蓋.G的最小覆蓋的節點數稱為G的覆蓋數，或點覆蓋數，常記為月(G)一個圖稱為覆蓋臨界圖，或點覆蓋臨界圖，若從這圖上去掉任何一條邊後，所得的圖的覆蓋數都小於原圖的覆蓋數.設有一個最小覆蓋M，若對於它的任何一個子集M'，與M‘中節點相鄰的不在M中的節點的數目總不比M‘的節點數少，則稱M為一個外部最小覆蓋或外最小點覆蓋.不是任何一圖都有外最小覆蓋.事實上，一個圖有外最小覆蓋當且僅當它有一個點核，或邊核. ^[1]