数学|平面图与图着色-yiteyi-C++库

先决条件—— 图论基础考虑具有多个节点之间的连接的电子电路。是否可以在一块电路板上打印该电路，使所有连接都不相互交叉，即不重叠或相交？如果我们知道 平面性 一系列的图表。

null

平面性—— “如果图形可以在平面上绘制，则称其为平面图形 没有任何交叉 .这样的图形称为图形的平面表示。”

重要提示—— 一个图形可能是平面的，即使它是用交叉点绘制的，因为在没有交叉点的情况下，它可能以不同的方式绘制。例如，考虑完整的图 $K_{4}$ 以及它的两种可能的平面表示—— 图片[2]-数学|平面图与图着色-yiteyi-C++库

例如—— 是超立方体吗 $Q_{3}$ 平面的？
解决方案—— 对 $Q_{3}$ 是平面的。它的平面表示-

平面图中的区域——

图的平面表示法将平面拆分为区域。这些区域由边限定，但有一个区域是无界的。例如，考虑下面的图表图片[7]-数学|平面图与图着色-yiteyi-C++库共有6个区域，其中5个有界区域和1个无界区域 $R_{6}$ . 图的所有平面表示都在相同数量的区域中分割平面。欧拉发现平面图中的区域数是图中顶点数和边数的函数。

定理—— “让我 $G$ 做一个 连通简单平面图 具有 $e$ 边缘和 $v$ 顶点。然后是区域的数量 $r$ 在图中等于 $e-v+(k+1)$ 其中k是图中组件的数量。 .”

例如—— 有20个顶点且每个顶点的阶数为3的连通平面简单图中的区域数是多少？
解决方案—— 边缘度数之和=20*3=60。通过握手定理， $2e = 60$ 这给了 $e = 30$ . 根据欧拉定理，区域数= $e - v + 2$ 它给出了12个区域。

欧拉公式得到的一个重要结果是以下不等式——

注—— “如果 $G$ 是一个连通平面图 $e$ 边缘和 $v$ 顶点，在哪里 $vgeq 3$ 然后 $eleq 3v - 6$ 而且 $G$ 顶点的度数不能超过5。“

例如—— 这是图表 $K_{5}$ 平面的？
解决方案—— 中的顶点和边数 $K_{5}$ 分别是5和10。因为10>3*5–6，10>9不平等 $eleq 3v - 6$ 他并不满意。因此，图形不是平面的。

图着色-

如果你决定创建一张地图，并且需要对地图的各个部分进行最佳着色，那么你应该感到幸运，因为图论就在你身边。为地图的各个区域着色所需的最大颜色数是多少？这个问题和其他类似的问题在图论中产生了许多结果。首先，让我们以一种形式化的方式定义着色的约束-

着色—— “简单图的着色是将一种颜色分配给图的每个顶点，使得 没有两个相邻的顶点 都被指定为相同的颜色。”

解决这个问题的一个简单方法是用不同的颜色给每个顶点上色，以得到总的颜色 $v$ 颜色。但在某些情况下，实际需要的颜色数量可能会少于此数量。

色数- “给图形上色所需的最少颜色数称为其颜色色数 .表示为 $chi (G)$ .”

对于平面图，求色数与求平面图着色所需的最小颜色数是相同的问题。

4颜色定理—— “平面图的色数不大于4。”

例1- 下列图的色数是多少？
解决方案—— 在图形中 $G$ ，自顶点起，色数至少为3 $a$ , $b$ 和 $f$ 它们彼此相连。以下颜色指定满足着色约束—— $a$ –红色 $b$ –绿色 $c$ -蓝色 $d$ –红色 $e$ –绿色 $f$ -蓝色 $g$ –红色因此，色数 $G$ 3岁。在图形中 $H$ 自从 $a$ 和 $d$ 都是连通的，因此色数为4。
例2- 颜色数是多少 $K_{n}$ ?
解决方案—— 因为在一个完整的图中，每个顶点都与其他顶点相连，所以色数是 $n$ .
例3- 颜色数是多少 $C_{n}$ ?
解决方案—— 如果顶点以交替方式着色，则循环图需要2种颜色。如果 $n$ 如果是奇数，那么最后一个顶点的颜色将与第一个顶点的颜色相同，因此色数将为3。但如果它是偶数，那么第一个顶点和最后一个顶点将是不同的颜色，颜色数将是2。
例4- 颜色数是多少 $K_{m,n}$ ?
解决方案—— 在二部图中 $K_{m,n}$ ，将中的顶点分为两组，以便同一组中的顶点之间没有边。因此，任何二部图的色数都是2。一组顶点可以指定一种颜色，另一组顶点可以指定一种不同的颜色，总共有两种颜色。它将满足着色约束，因为同一集合的顶点没有连接。