text: 在圖論中，圖的邊覆蓋是指一組邊的集合，且該集合滿足圖的每個頂點都在至少一條邊上。在計算機科學中，最小邊覆蓋問題是尋找最小個數邊的邊覆蓋問題。它是屬於覆蓋問題類的最佳化問題，可以在多項式時間內求解。定義.正式來說，圖"G"的邊覆蓋是指一組邊的集合"C" ，其滿足"G"中的每個頂點都至少在"C"中的一條邊上。其被描述為集合"C覆蓋"了"G"中的所有頂點。下圖顯示了兩個圖中邊緣覆蓋的示例。最小邊覆蓋是指最小可能數量的邊覆蓋。邊覆蓋數formula_1是最小邊覆蓋的數量。下圖中的紅線為最小邊覆蓋的示例。注意右圖不但是邊覆蓋，而且是滿足匹配的。它是一種特殊情況——完美匹配：在一個匹配"M"中，每個頂點都恰好只在一條邊上。完美匹配一定是最小邊覆蓋。演算法.透過找到一個最大基數匹配並貪婪地擴充套件它直到覆蓋所有頂點，可以在多項式時間內找到最小的邊緣覆蓋。 在下圖中，最大基數匹配用紅色標記；為覆蓋不匹配節點而新增的額外邊用藍色標記。 （右圖的最大基數匹配是完美匹配；因此它已經覆蓋了所有頂點，不再需要額外的邊去覆蓋。 )另一方面來說，尋找最小點覆蓋的相關問題是一個NP困難問題。
metadata.dataset: erhwenkuo/wikipedia-zhtw
metadata.title: 邊覆蓋
metadata.url: https://zh.wikipedia.org/wiki?curid=7974213