数据结构
网络
关系数据库管理系统 (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
广告