离散数学中的平面图

如果我们想学习可平面图，我们必须了解图。图可以描述为顶点集合，这些顶点通过一组边相互连接。我们也可以将图的研究称为图论。在本节中，我们将学习可平面图的定义、性质以及可平面图的例子。

可平面图

可平面图是指可以在平面上绘制，并且其任何两条边都不相交的图。可平面图的简单示例如下：

上面的图没有两条边相交。因此，这个图是一个可平面图。

平面区域

在图的可平面表示过程中，平面被分割成相连的区域，这些区域被称为平面区域。

每个区域都有一定的度数。这些度数描述如下：

• 内部区域的度数等于包围该区域的边数。
• 同样，外部区域的度数等于暴露给该区域的边数。

平面区域示例

在这个例子中，我们将考虑一个可平面图，描述如下：

在上面的可平面图中，我们可以看到该图将平面分割成 4 个区域，即 R1、R2、R3 和 R4，这些区域的度数描述如下：

Degree (R1) = 3
Degree (R2) = 3
Degree (R3) = 3
Degree (R4) = 5

可平面图的色数

• 在任何可平面图中，色数必须始终小于或等于 4。
• 因此，要给任何可平面图的顶点着色，我们最多需要 4 种颜色。

可平面图的性质

可平面图有多种性质，其中一些描述如下：

性质 1：所有顶点的度数之和等于图中边数的两倍。该性质的符号表示如下：

性质 2：所有区域的度数之和等于图中边数的两倍。该性质的符号表示如下：

有一些特殊情况，描述如下：

情况 1：如果每个区域的度数都是 k，则可平面图将包含以下关系：

情况 2：如果每个区域的最小度数是 k (>=k)，则可平面图将包含以下关系：

情况 3：如果每个区域的最大度数是 k (<=k)，则可平面图将包含以下关系：

性质 3：如果有一个简单的可平面图 G，它包含 'v' 个顶点、'e' 条边和 'r' 个区域，那么它们之间的关系描述如下：

我们可以称上述公式为欧拉公式。

在图的可平面表示的所有形式中，此公式保持不变。

性质 4：假设有一个可平面图 G，它包含 k 个连通分量。它们之间的关系描述如下：

可平面图的例子

可平面图有各种各样的例子，其中一些描述如下：

例 1：在这个例子中，我们有一个可平面图 G，它包含 60 条边和 25 个顶点。现在我们需要确定图 G 中区域的数量。

解：根据问题，我们有关于图 G 的以下详细信息：

顶点数 (v) = 25

边数 (e) = 60

利用欧拉公式，我们有 r = e - v + 2。

现在我们将 v 和 e 的值代入此公式，得到以下详细信息：

r = 60 - 25 + 2

r = 37

因此，图 G 中的区域总数为 37。

例 2：在这个例子中，我们有一个简单的可平面图 G，它包含 9 条边、10 个顶点和 3 个连通分量。现在我们需要确定图 G 中区域的数量。

解：根据问题，我们有关于图 G 的以下详细信息：

顶点数 (v) = 10

连通分量数 (k) = 3

边数 (e) = 9

利用欧拉公式，我们有 r = e - v + (k+1)。

现在我们将 v、e 和 k 的值代入此公式，得到以下详细信息：

r = 9-10+ (3+1)

r = -1+4

r = 3

因此，图 G 中的区域总数为 3。

例 3：在这个例子中，我们有一个简单的可平面图 G，它包含 20 个顶点，且每个顶点的度数都为 3。现在我们需要确定图 G 中区域的数量。

解：根据问题，我们有关于图 G 的以下详细信息：

每个顶点的度数 (d) = 3

顶点数 (v) = 20

计算总边数 (e)

当我们进行顶点度数之和定理的计算时，我们得到以下关系：

所有顶点的度数之和等于总边数的两倍。

每个顶点的度数 * 顶点数等于总边数的两倍。

因此，我们将使用每个顶点的度数公式得到以下结果：

20*3 = 2*e

e = 30

因此，在图 G 中，总边数为 30。

计算总区域数 (r)

利用欧拉公式，我们有 r = e - v + 2。

当我们把 v 和 e 的值代入这个公式时，我们得到以下详细信息：

区域数 (r) = 30-20+2

r = 12

因此，在图 G 中，区域总数为 12。

例 4：在这个例子中，我们有一个简单的可平面图 G，它包含 35 个区域，且每个区域的度数都为 6。现在我们需要确定图 G 中顶点的数量。

解：根据问题，我们有关于图 G 的以下详细信息：

每个区域的度数 (d) = 6

区域数 (n) = 35

计算总边数 (e)

当我们进行区域度数之和定理的计算时，我们得到以下关系：

所有区域的度数之和等于总边数的两倍。

每个区域的度数 * 区域数等于总边数的两倍。

35*6 = 2*e

e = 105

因此，在图 G 中，总边数为 105。

计算总顶点数 (v)

利用欧拉公式，我们有 r = e - v + 2。

当我们把 r 和 e 的值代入这个公式时，我们得到以下详细信息：

35 = 105 - v + 2

v = 72

因此，在图 G 中，顶点总数为 72。

例 5：在这个例子中，我们有一个简单的可平面图 G，它包含 30 条边、12 个顶点，并且每个区域的度数为 k。现在我们需要确定 k 的值。

解：根据问题，我们有关于图 G 的以下详细信息：

边数 (e) = 30

每个区域的度数 (d) = k

顶点数 (v) = 12

计算总区域数 (r)

利用欧拉公式，我们有 r = e - v + 2。

当我们把 v、d 和 e 的值代入这个公式时，我们得到以下详细信息：

区域数 (r) = 30-12+2

r = 20

因此，在图 G 中，区域总数为 20。

计算 k 的值

当我们进行区域度数之和定理的计算时，我们得到以下关系：

所有区域的度数之和等于总边数的两倍。

每个区域的度数 * 区域数等于总边数的两倍。

20*k = 2*30

k = 30

因此，在图 G 中，每个区域的度数为 3。

例 6：在这个例子中，我们有一个简单的可平面图 G，它包含 10 条边。现在我们需要确定该图中可能存在的最大区域数。

解：我们知道简单的可平面图包含以下内容：

每个区域的度数 >= 3。

因此，我们有以下详细信息：

3 * |R| <= 2 * |E|

现在我们将 |E| = 10 的值代入，得到以下详细信息：

3 * |R| <= 2* 10

|R| <= 6.67

|R| <= 6

因此，在图 G 中，最大区域数为 6。

例 7：在这个例子中，我们有一个简单的可平面图 G，它包含 15 个区域。现在我们需要确定该图中可能存在的最大边数。

解：我们知道简单的可平面图包含以下内容：

每个区域的度数 >= 3

因此，我们有以下详细信息：

3 * |R| <= 2 * |E|

现在我们将 |R| = 15 的值代入，得到以下详细信息：

3 * 15 <= 2* |E|

|E| >= 22.5

|E| >= 23

因此，在图 G 中，最大边数为 23。