邊覆蓋
在圖論中，圖的邊覆蓋是指一組邊的集合，且該集合滿足圖的每個頂點都在至少一條邊上。在計算機科學中，最小邊覆蓋問題是尋找最小個數邊的邊覆蓋問題。它是屬於覆蓋問題類的優化問題，可以在多項式時間內求解。
| 線性規劃問題：覆蓋/包裝問題對 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||
定義[編輯]
正式來說，圖G的邊覆蓋是指一組邊的集合C ，其滿足G中的每個頂點都至少在C中的一條邊上。其被描述為集合C覆蓋了G中的所有頂點。下圖顯示了兩個圖中邊緣覆蓋的示例。
最小邊覆蓋是指最小可能數量的邊覆蓋。邊覆蓋數是最小邊覆蓋的數量。下圖中的紅線為最小邊覆蓋的示例。
注意右圖不但是邊覆蓋，而且是滿足匹配的。它是一種特殊情況——完美匹配：在一個匹配M中，每個頂點都恰好只在一條邊上。完美匹配（如果存在）一定是最小邊覆蓋。
例子[編輯]
- 所有邊的集合(若沒有度為 0 的頂點)。
- 完全二分圖K m, n的邊覆蓋數為m和n中的較大值。
算法[編輯]
通過找到一個最大基數匹配並貪婪地擴展它直到覆蓋所有頂點，可以在多項式時間內找到最小的邊緣覆蓋。 [1] [2]在下圖中，最大基數匹配用紅色標記；為覆蓋不匹配節點而添加的額外邊用藍色標記。 （右圖的最大基數匹配是完美匹配；因此它已經覆蓋了所有頂點，不再需要額外的邊去覆蓋。 )
另一方面來說，尋找最小點覆蓋的相關問題是一個NP困難問題。 [1]
參見[編輯]
注釋[編輯]
- ^ 1.0 1.1 Garey & Johnson (1979), p. 79, uses edge cover and vertex cover as one example of a pair of similar problems, one of which can be solved in polynomial time while the other one is NP-hard. See also p. 190.
- ^ Lawler, Eugene L., Combinatorial optimization: networks and matroids, Dover Publications: 222–223, 2001 [2022-05-11], ISBN 978-0-486-41453-9, （原始內容存檔於2022-05-11）.
參考文獻[編輯]
- Weisstein, Eric W. (編). Edge Cover. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.
- Garey, Michael R.; Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5.