-
邊覆蓋
鎖定
邊覆蓋是一類覆蓋，指一類邊子集。具體地説，圖的一個邊子集，使該圖上每一節點都與這個邊子集中的一條邊關聯，只有含孤立點的圖沒有邊覆蓋，邊覆蓋也稱為邊覆蓋集，圖G的最小邊覆蓋就是指邊數最少的覆蓋，圖G的最小邊覆蓋的邊數稱為G的邊覆蓋數，常記為β′(G)。
[1]
- 中文名
- 邊覆蓋
- 外文名
- edge covering
- 所屬學科
- 數學
- 別 名
- 邊覆蓋集
- 定 義
- 圖的一個邊子集
邊覆蓋定義
設圖
，若
，使得v與e相關聯，則稱e覆蓋v，並稱
為邊覆蓋集，或簡稱邊覆蓋。設
為邊覆蓋，若
的任何真子集都不是邊覆蓋，則稱
是極小邊覆蓋。邊數最少的邊覆蓋集稱為最小邊覆蓋，其所含邊的個數稱為邊覆蓋數，記作
，或簡記為
。
[2]
在圖1(a)中，
都是極小邊覆蓋，其中
是最小邊覆蓋，
。(b)中
都是極小邊覆蓋，
。
圖1（a）
圖1（b）
邊覆蓋相關概念
設
，若
中任何兩條邊均不相鄰，則稱
為G中邊獨立集，也稱
為G中的匹配。若在
中再加任意一條邊後，所得集合都不是匹配，則稱
為極大匹配。邊數最多的匹配稱為最大匹配，其邊數稱為獨立數或匹配數，記作
或簡記為
。
[2]
在圖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)中的一個最小邊覆蓋，比如
，從中移去一條相鄰的邊，則
都是圖中的最大匹配，這種由最大匹配通過增加關聯非飽和點的邊產生最小邊覆蓋，和由最小邊覆蓋通過移去相鄰的一條邊產生最大匹配的方法具有普遍性。
[2]
邊覆蓋相關定理
邊覆蓋定理1
設n階圖G中無孤立點。
(1)設M為G中的一個最大匹配，對於G中每個M-非飽和點均取一條與其關聯的邊，組成邊集N，則
為G中最小邊覆蓋。
(2)設
為G中的一個最小邊覆蓋，若
中存在相鄰的邊就移去其中的一條，設移去的邊集為
，則
為G中一個最大匹配。
(3)G中邊覆蓋數
與匹配數
滿足：
。
邊覆蓋推論1
圖2（a）
圖2（b）
圖2（c）
邊覆蓋定理2
證明:
必要性 設M為G中最大匹配，若G中存在M的可增廣的交錯路徑
，則
在M中的邊比不在M中的少1。設
(
為對稱差運算)，則M’中邊彼此不相鄰且M’比M多一條邊，即M’是比M多一條邊的匹配，這與M是最大匹配相矛盾，所以M不含可增廣的交錯路徑。
