臨界邊

臨界邊(critical edge)是圖論的基本概念之一，臨界邊是這樣的邊：從一個圖上去掉它之後，能使所得圖的點覆蓋數減小。設e是G上一條邊，若點覆蓋數β(G-e)<β(G)，則稱e是G的關於點覆蓋的臨界邊，簡稱臨界邊。若G的每一條邊都是關於點覆蓋的臨界邊，則稱G為關於點覆蓋的邊臨界圖。

基本介紹

• 中文名：臨界邊
• 外文名：critical edge
• 所屬學科：數學
• 屬性：圖論的基本概念之一
• 所屬問題：圖論
• 相關概念：點覆蓋數，邊覆蓋數等

定義

圖G的一個匹配M稱為G的一個邊獨立集，G的最大匹配所含的邊數稱為G的邊獨立數或匹配數。記為 。

在一個圖中，如果刪除一條邊將使得獨立數增加，則稱該邊是臨界的，對於一對不相鄰的頂點，如果添加一條邊把它們連線起來將會使得獨立數增加，則稱這一對頂點是準-臨界的。

註：邊獨立集與點覆蓋有密切關係，由於任意一個頂點不能覆蓋邊獨立集中的兩條邊，因此圖有大的邊獨立集，就有大的點覆蓋集。另一方面，邊獨立集中不同的邊不能用同一個頂點覆蓋，因此圖G中任何點覆蓋集所含的點數不會小於任何邊獨立集含的邊數。

臨界邊的性質

下述為可分圖中臨界邊的一些性質。

定理1對於可分圖中的邊 ，下面的命題等價：

A)是臨界邊；

B) ；

C)屬於 個最大團。

證明: ： 是 中大小為 的穩定集。

：如果 是臨界的，則有一個集合S使得 和 均是G中的最大穩定集。因此，包含x但不包含y的任意最大團均不與相交。由於有個包含x的最大團，而與不相交的最大團卻只有一個，其餘的個包含x的最大團必然也包含y。

：在唯一的著色方案中，穩定集就是包含x的那些團的配偶。由於屬於個最大團。這個團的配偶同時屬於和。這使得圖中僅剩下了個頂點，其中包含頂點和穩定集S，並且和。

推論 設G是一個可分圖，如果邊不出現在任何最大團中，則是可分的。如果是未出現在任何最大穩定集中的不相鄰頂點，則是可分的。

證明： 根據互補性，我們只需證明第一個命題，如果我們刪掉未出現在任何最大團中的一條邊，則由定理1得出它不是臨界邊，故我們有，因為我們並沒有破壞任何一個最大團也沒有產生更大的穩定集，所以我們可以利用最優著色和的團劃分來得出結論：並且。因此，是可分的。

相關概念

點覆蓋數

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

點核

點核(vertex core)是圖論的一個重要概念，指圖的一個子圖，由圖G的基數與G的邊覆蓋數相等的所有獨立集的並所產生的節點導出子圖，稱為G的點核。並非所有的圖都存在點核，由G的基數與G的點覆蓋數相等的所有邊獨立集的並所產生的邊導出子圖，稱為G的邊核。同樣，並非所有的圖都有邊核。但已證明：一個圖有點核若且唯若它有邊核；且它們都與存在外最小覆蓋等價。