資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究線/邊覆蓋
覆蓋圖是一個子圖，它包含與另一個圖對應的所有頂點或所有邊。包含所有頂點的子圖稱為**線/邊覆蓋**。包含所有邊的子圖稱為**頂點覆蓋**。
線覆蓋
設 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' 的所有組成部分都是星形圖，並且從星形圖中無法刪除任何邊。
更新於: 2019年8月23日
240 次瀏覽
廣告