制約集

制約集(dominating set)是圖論的一個重要概念，指一個圖的特殊節點子集，設A是圖G的一個節點子集，若G的任何不在A中的節點都與A中的節點相鄰，則稱A為G的一個制約集，圖G的最小制約集的基數稱為G的制約數，也稱外固數。

基本介紹

• 中文名：制約集
• 外文名：dominating set
• 所屬學科：數學
• 所屬問題：組合學(圖與超圖)
• 簡介：圖論的一個重要概念

全制約集

全制約集是圖的一種特殊的制約集，具體地說，設有圖G的一個節點子集A，若對於G上任一節點u，A中存在與u相鄰的節點，則稱A為G的一個全制約集，事實上，只有含孤立點的圖上才不存在全制約集，含節點數最少的全制約集稱為最小全制約集，不含孤立點的圖的最小全制約集中的節點數稱為全制約數，設有不含孤立點的圖的節點集的一個劃分，若這一划分的每一個節點子集都是G的全制約集，則稱該劃分為一個全制約劃分，全制約劃分數就是指在G的所有全制約劃分中，劃分所得的節點子集最多的那一個劃分的子集數目。

獨立制約集

獨立制約集是圖論的一個重要概念，指圖的一種節點子集，具體地說，一個圖的既是獨立集又是制約集的節點子集，稱為該圖的獨立制約集，圖的最小獨立制約集的基數稱為它的獨立制約數，若圖G的節點集可以劃分為若干個兩兩不交的獨立制約集，則稱G可獨立制約劃分。

連通制約集

連通制約集是圖的一種特殊制約集，具體地說，若A是圖G的制約集，且A在G中的導出子圖是連通的，則稱A是G的連通制約集，G的節點數最少的連通制約集的節點數稱為G的連通制約數，圖G的節點集若可以劃分為若干個兩兩不相交的連通制約集，則在G的所有這樣的劃分中，基數最大的劃分的基數稱為G的連通制約劃分數。

制約劃分

制約劃分是圖論的一個重要概念，指圖的節點集的一種劃分，具體地說，一個圖G的制約劃分，就是把G的節點集分為若干個互不相交的子集，每一個子集都是G的制約集，在G的所有制約劃分中，劃分出的子集最多的那一個劃分的子集的數目稱為G的制約劃分數。