图论 - 独立集
独立集用集合表示，其中
不应该有**任何彼此相邻的边**。任何两条边之间不应该有公共顶点。
不应该有**任何彼此相邻的顶点**。任何两个顶点之间不应该有公共边。
独立线集
设“G” = (V, E) 为一个图。E 的一个子集 L 称为“G”的独立线集，如果 L 中的任何两条边都不相邻。这样的集合称为独立线集。
例子
让我们考虑以下子集 -
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 的线覆盖数，
$$\alpha 1 = \lceil\frac{n}{2}\rceil\begin{cases}\frac{n}{2}\:如果\:n\:是偶数 \\\frac{n+1}{2}\:如果\:n\:是奇数\end{cases}$$线独立数（匹配数）= β1 = [n/2] α1 + β1 = n。
独立顶点集
设“G” = (V, E) 为一个图。“V”的一个子集称为“G”的独立集，如果“S”中的任何两个顶点都不相邻。
例子
考虑上面图中以下子集 -
S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}
显然 S1 不是一个独立顶点集，因为要获得一个独立顶点集，图中至少需要两个顶点。但这里情况并非如此。子集 S2、S3 和 S4 是独立顶点集，因为没有一个顶点与子集中的任何一个顶点相邻。
最大独立顶点集
设“G”为一个图，则“G”的一个独立顶点集被称为最大独立顶点集，如果“G”的任何其他顶点都不能添加到“S”。
例子
考虑上面图中以下子集。
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)。
例子
对于完全图 Kn，
顶点覆盖数 = α2 = n−1
顶点独立数 = β2 = 1
你有 α2 + β2 = n
在一个完全图中，每个顶点都与其剩余的 (n − 1) 个顶点相邻。因此，Kn 的最大独立集只包含一个顶点。
因此，β2=1
并且 α2=|v| − β2 = n-1
注意 - 对于任何图“G” = (V, E)
- α2 + β2 = |v|
- 如果“S”是“G”的一个独立顶点集，则 (V – S) 是 G 的顶点覆盖。