臨界邊檢視原始碼討論檢視歷史

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

[]

相關概念

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

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

定義

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

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

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