邊覆蓋

邊覆蓋是一類覆蓋，指一類邊子集。具體地說，圖的一個邊子集，使該圖上每一節點都與這個邊子集中的一條邊關聯，只有含孤立點的圖沒有邊覆蓋，邊覆蓋也稱為邊覆蓋集，圖G的最小邊覆蓋就是指邊數最少的覆蓋，圖G的最小邊覆蓋的邊數稱為G的邊覆蓋數，常記為β′(G)。

基本介紹

• 中文名：邊覆蓋
• 外文名：edge covering
• 所屬學科：數學
• 別稱：邊覆蓋集

定義

設圖，若，使得v與e相關聯，則稱e覆蓋v，並稱為邊覆蓋集，或簡稱邊覆蓋。設為邊覆蓋，若的任何真子集都不是邊覆蓋，則稱是極小邊覆蓋。邊數最少的邊覆蓋集稱為最小邊覆蓋，其所含邊的個數稱為邊覆蓋數，記作，或簡記為。

在圖1(a)中，都是極小邊覆蓋，其中是最小邊覆蓋，。(b)中都是極小邊覆蓋，。

圖1（a）

圖1（b）

相關概念

設，若中任何兩條邊均不相鄰，則稱為G中邊獨立集，也稱為G中的匹配。若在中再加任意一條邊後，所得集合都不是匹配，則稱為極大匹配。邊數最多的匹配稱為最大匹配，其邊數稱為獨立數或匹配數，記作或簡記為。

在圖1(a)中，都是極大匹配，其中是最大匹配，。(b)中都是極大匹配，同時也都是最大匹配，。

常用M表示匹配，極大匹配，最大匹配等。

設M為圖G中一個匹配。

(1)設，則稱與被M所匹配。

(2)對於任意的，若存在邊e∈M，使e與v關聯，則稱v為M-飽和點．否則稱v為M-非飽和點。

(3)若G中每個頂點都是M-飽和點，則稱M為G中的完美匹配。

(4)稱G中在M和(E(G)-M)中交替取邊的路徑為M的交錯路徑，起點和終點都是M-非飽和點的交錯路徑稱為可增廣的交錯路徑。稱G中在M和(E(G)-M)中交替取邊的圈為交錯圈。

在圖2(a)中，為完美匹配，(b)中不可能有完美匹配，因而對任何匹配都存在著M-非飽和點。

另外，在圖1(a)中的最大匹配，它也是圖中的最小邊覆蓋。而在(b)中，任給一個最大匹配，比如．則，都是圖中的最小邊覆蓋。反之，給定(b)中的一個最小邊覆蓋，比如，從中移去一條相鄰的邊，則都是圖中的最大匹配，這種由最大匹配通過增加關聯非飽和點的邊產生最小邊覆蓋，和由最小邊覆蓋通過移去相鄰的一條邊產生最大匹配的方法具有普遍性。

相關定理

定理1

設n階圖G中無孤立點。

(1)設M為G中的一個最大匹配，對於G中每個M-非飽和點均取一條與其關聯的邊，組成邊集N，則為G中最小邊覆蓋。

(2)設為G中的一個最小邊覆蓋，若中存在相鄰的邊就移去其中的一條，設移去的邊集為，則為G中一個最大匹配。

(3)G中邊覆蓋數與匹配數滿足：。

推論1

設G是n階無孤立點的圖。M為G中的匹配，W是G中的邊覆蓋，則。等號成立時,M為G中完美匹配。

圖2（a）

圖2（b）

圖2（c）

定理2

M為G中的最大匹配若且唯若G中不含M可增廣的交錯路徑。

證明:

必要性 設M為G中最大匹配，若G中存在M的可增廣的交錯路徑，則在M中的邊比不在M中的少1。設(為對稱差運算)，則M’中邊彼此不相鄰且M’比M多一條邊，即M’是比M多一條邊的匹配，這與M是最大匹配相矛盾，所以M不含可增廣的交錯路徑。

充分性 設M是G中不含可增廣的交錯路徑的匹配，是G中的最大匹配，只要證明。為此，考慮和M對稱差的導出子圖，設。當(空圖)時，，於是M為G中最大匹配。若，由於M，都是匹配，所以H各連通分支要么是由M和中的邊組成的交錯圈，在交錯圈上M和中的邊數相等，要么為由M和中的邊組成的交錯路徑。由已知條件可知M不含可增廣的交錯路徑，是最大匹配，由必要性可知，中也無可增廣的交錯路徑，於是在由M和組成的交錯路徑上，M和的邊也相等，總之M和邊的個數相同，所以M為最大匹配。