离散数学中的图的补集

在离散数学中，简单图用 G 表示，该图的补集用 G` 表示。如果 G` 是简单图 G 的补集，那么它必须包含以下内容：

• 补图必须包含图 G 的所有顶点。
• 如果存在两个顶点 v 和 w，并且原始图 G 之间没有边连接这两个顶点，在这种情况下，补图必须在这两个顶点 v 和 w 之间包含一条边。

图的补集的简单示例描述如下：

在这个例子中，我们左边有一个简单图，表示为 G，右边是它的补图，表示为 G`。

G 和 G` 之间的关系

简单图 G 和补图 G` 之间存在一些关系，描述如下：

1. 图 G 中的顶点数等于其补图 G1` 中的顶点数。此关系的符号表示如下：

2. 两个图（即简单图 G 及其补图 G`）的总边数之和等于完全图的总边数。此关系的符号表示如下：

这里 n 用于表示图中的总顶点数。

重要提示

当学习图的补集这个术语时，我们应该知道一些要点，描述如下：

1. 图的大小等于图中的总顶点数。
2. 与图的大小相同，图的阶等于图中的顶点数。

图的补集的例子

图的补集有各种各样的例子，其中一些描述如下：

示例 1：在此示例中，我们有一个简单图 G，包含 21 条边和 10 个顶点。现在我们将计算图 G` 中的边数。

解决方案：从问题中，我们得到关于图 G 的以下详细信息：

顶点数 n = 10

边数 |E(G)| = 21

我们知道 |E(G)| + |E(G`)| = n(n-1) /2

现在我们将 n 和 |E(G)| 的值代入该公式，得到以下详细信息：

21 + |E(G`)| = 10*(10-1) /2

| E(G`)| = 45-21

|E(G`)| = 24

示例 2：在此示例中，我们有一个简单图 G 和一个补图 G`。图 G 包含 30 条边，G` 包含 36 条边。现在我们将计算图 G 中的顶点数。

解决方案：从问题中，我们得到以下信息：

在图 G 中，边数 |E(G)| = 30

在图 G` 中，边数 |E(G`)| = 36

我们知道 |E(G)| + |E(G`)| = n(n-1) /2

现在我们将 |E(G)| 和 |E(G`)| 的值代入该公式，得到以下详细信息：

30+36 = n(n-1) /2

n(n-1) = 132

n² - n - 132 = 0

现在我们将用二次方程来求解上述方程。二次方程描述如下：

n = (-b ± √b² - 4ac) / 2a

当方程处于标准形式时，我们将从原始方程 n² - n - 272 = 0 中找到 a、b 和 c 的值，并将它们代入上述二次公式，如下所示：

n² - n - 132 = 0

a = 1

b = -1

c = -132

n = {-(-1) ± √(-1)² - 4*1*(-132))} / 2*1

n = {1 ± √1 - (-528)} /2

n = {1 ± 23)} /2

n = 24 /2

n = 12

因此，图 G 的顶点数为 G = 12。

示例 3：在此示例中，我们有一个简单图 G，其阶为 n。这里简单图 G 的大小为 56，其补图 G` 的大小为 80。现在我们将求出 n 的值。

解决方案：图的大小 = 图中的边数

从问题中，我们得到以下信息：

在图 G 中，边数 |E(G)| = 56

在图 G` 中，边数 |E(G`)| = 80

我们知道 |E(G)| + |E(G`)| = n(n-1) /2

现在我们将 |E(G)| 和 |E(G`)| 的值代入，得到以下详细信息：

56+80 = n(n-1) /2

n(n-1) = 272

n² - n - 272 = 0

现在我们将用二次方程来求解这个方程。二次方程描述如下：

n = (-b ± √b² - 4ac) / 2a

当方程处于标准形式时，我们将从原始方程 n² - n - 272 = 0 中找到 a、b 和 c 的值，并将它们代入上述二次公式，如下所示：

n² - n - 272 = 0

a = 1

b = -1

c = -272

n = {-(-1) ± √(-1)² - 4*1*(-272))} / 2*1

n = {1 ± √1 + 1088)} /2

n = {1 ± 33}

n = 34 /2

n = 17

因此，图 G 的顶点数为 G = 17。

换句话说，我们可以说图 G 的阶为 17。