覆蓋集

覆蓋集

覆蓋集是一個數學術語。

基本介紹

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

相關詞條

熱門詞條

聯絡我們