資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學獨立線集
獨立集在集合中表示，其中
不應該有**任何相互鄰接的邊**。任何兩條邊之間不應該有任何公共頂點。
不應該有**任何相互鄰接的頂點**。任何兩個頂點之間不應該有任何公共邊。
獨立線集
設'G' = (V, E) 為一個圖。如果L的任意兩條邊都不相鄰，則E的子集L稱為'G'的獨立線集。這樣的集合稱為獨立線集。
示例
讓我們考慮以下子集：
L1 = {a,b}
L2 = {a,b} {c,e}
L3 = {a,d} {b,c}在這個例子中，子集L2和L3顯然不是給定圖中的相鄰邊。它們是獨立線集。然而，L1不是獨立線集，因為要構成獨立線集，至少需要兩條邊。
最大獨立線集
如果不能將'G'的任何其他邊新增到'L'，則稱獨立線集為圖'G'的最大獨立線集。
示例
讓我們考慮以下子集：
L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}L2和L3是最大獨立線集/最大匹配。因為只有對於這兩個子集，才沒有機會新增任何非鄰接邊。因此，這兩個子集被認為是最大獨立線集。
最大獨立線集
具有最大邊數的'G'的最大獨立線集稱為'G'的最大獨立線集。
Number of edges in a maximum independent line set of G (β1) = Line independent number of G = Matching number of G
示例
讓我們考慮以下子集：
L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}L3是G的最大獨立線集，具有最多的不相鄰邊，用**β1** = 3表示。
**注意** - 對於任何沒有孤立頂點的圖G，
α1 + β1 = 圖中頂點數 = |V|
示例
Kn/Cn/wn的線覆蓋數，
線獨立數（匹配數）= **β1 = ⌊ n 2 ⌋ α1 + β1 = n**
更新於：2019年8月23日
瀏覽量：285
廣告