圖論 - 覆蓋
覆蓋圖是一個子圖，它包含所有頂點或所有邊，對應於另一個圖。包含所有頂點的子圖稱為**線/邊覆蓋**。包含所有邊的子圖稱為**頂點覆蓋**。
線覆蓋
令 G = (V, E) 為一個圖。如果 G 的每個頂點至少與 C 中的一條邊關聯，則子集 C(E) 稱為 G 的線覆蓋，即：
deg(V) ≥ 1 ∀ V ∈ G
因為每個頂點都透過一條邊與另一個頂點連線。因此，它具有至少 1 的最小度數。
示例
請檢視以下圖表 -
其具有線覆蓋的子圖如下 -
C1 = {{a, b}, {c, d}}
C2 = {{a, d}, {b, c}}
C3 = {{a, b}, {b, c}, {b, d}}
C4 = {{a, b}, {b, c}, {c, d}}
當且僅當 'G' 具有孤立頂點時，'G' 的線覆蓋不存在。具有 'n' 個頂點的圖的線覆蓋至少具有 [n/2] 條邊。
最小線覆蓋
如果無法從 C 中刪除任何邊，則圖 G 的線覆蓋 C 被稱為最小**線覆蓋**。
示例
在上圖中，具有線覆蓋的子圖如下 -
C1 = {{a, b}, {c, d}}
C2 = {{a, d}, {b, c}}
C3 = {{a, b}, {b, c}, {b, d}}
C4 = {{a, b}, {b, c}, {c, d}}
這裡，C1、C2、C3 是最小線覆蓋，而 C4 不是，因為我們可以刪除 {b, c}。
最小線覆蓋
它也稱為**最小最小線覆蓋**。具有最少邊數的最小線覆蓋稱為 'G' 的最小線覆蓋。'G' 的最小線覆蓋中的邊數稱為 'G' 的**線覆蓋數**(α1)。
示例
在上例中，C1 和 C2 是 G 的最小線覆蓋，α1 = 2。
每個線覆蓋都包含一個最小線覆蓋。
並非每個線覆蓋都包含一個最小線覆蓋（C3 不包含任何最小線覆蓋）。
沒有最小線覆蓋包含迴圈。
如果線覆蓋 'C' 不包含長度為 3 或更長的路徑，則 'C' 是一個最小線覆蓋，因為 'C' 的所有分量都是星形圖，並且從星形圖中，無法刪除任何邊。
頂點覆蓋
令 'G' = (V, E) 為一個圖。如果 'G' 的每條邊都與 'K' 中的頂點關聯或被其覆蓋，則 V 的子集 K 稱為 'G' 的頂點覆蓋。
示例
請檢視以下圖表 -
可以從上圖派生的子圖如下 -
K1 = {b, c}
K2 = {a, b, c}
K3 = {b, c, d}
K4 = {a, d}
這裡，K1、K2 和 K3 具有頂點覆蓋，而 K4 沒有頂點覆蓋，因為它沒有覆蓋邊 {bc}。
最小頂點覆蓋
如果無法從 'K' 中刪除任何頂點，則圖 'G' 的頂點 'K' 被稱為最小頂點覆蓋。
示例
在上圖中，具有頂點覆蓋的子圖如下 -
K1 = {b, c}
K2 = {a, b, c}
K3 = {b, c, d}
這裡，K1 和 K2 是最小頂點覆蓋，而在 K3 中，可以刪除頂點 'd'。
最小頂點覆蓋
它也稱為最小最小頂點覆蓋。具有最少頂點數的圖 'G' 的最小頂點覆蓋稱為最小頂點覆蓋。
'G' 的最小頂點覆蓋中的頂點數稱為 G 的頂點覆蓋數 (α2)。
示例
在下圖中，具有頂點覆蓋的子圖如下 -
K1 = {b, c}
K2 = {a, b, c}
K3 = {b, c, d}
這裡，K1 是 G 的最小頂點覆蓋，因為它只有兩個頂點。α2 = 2。