資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究獨立頂點集
獨立集用集合表示，其中
不應該有**任何彼此相鄰的邊**。任何兩條邊之間都不應該有公共頂點。
不應該有**任何彼此相鄰的頂點**。任何兩個頂點之間都不應該有公共邊。
獨立頂點集
設'G' = (V, E) 為一個圖。如果'S' 中的任何兩個頂點都不相鄰，則'V' 的子集稱為'G' 的獨立集。
示例
考慮上述圖形中的以下子集：
S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}顯然，S1 不是一個獨立頂點集，因為要獲得一個獨立頂點集，必須至少有兩個頂點以圖的形式存在。但這裡情況並非如此。子集 S2、S3 和 S4 是獨立頂點集，因為沒有頂點與子集中的任何頂點相鄰。
最大獨立頂點集
設'G' 為一個圖，則如果不能將'G' 的任何其他頂點新增到'S'，則'G' 的獨立頂點集稱為最大獨立頂點集。
示例
考慮上述圖形中的以下子集。
S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}S2 和 S3 是'G' 的最大獨立頂點集。在 S1 和 S4 中，我們可以新增其他頂點；但在 S2 和 S3 中，我們不能新增任何其他頂點。
最大獨立頂點集
具有最大頂點數的'G' 的最大獨立頂點集稱為最大獨立頂點集。
示例
考慮上述圖形中的以下子集：
S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}只有 S3 是最大獨立頂點集，因為它包含最多的頂點。'G' 的最大獨立頂點集中的頂點數稱為'G' 的獨立頂點數 (β2)。
示例
For the complete graph Kn, Vertex covering number = α2 = n-1 Vertex independent number = β2 = 1 You have α2 + β2 = n In a complete graph, each vertex is adjacent to its remaining (n − 1) vertices. Therefore, a maximum independent set of Kn contains only one vertex. Therefore, β2=1 and α2=|v| − β2 = n-1
注意 - 對於任何圖'G' = (V, E)
α2 + β2 = |v|
如果'S' 是'G' 的獨立頂點集，則 (V – S) 是'G' 的頂點覆蓋。
更新於：2019年8月23日
305 次瀏覽
廣告