平面图和非平面图

本文概述

• 平面图的性质
• 非平面图
• 非平面图的性质
• 图形着色
• 图形着色的应用
• 陈述并证明握手定理。

如果可以在平面中绘制图形, 以使没有边缘交叉, 则称该图形为平面。

示例：图中所示的图是平面图。

图的区域：考虑一个平面图G =（V, E）。一个区域定义为平面的一个区域, 该区域以边为边界并且无法进一步细分。平面图将平面图划分为一个或多个区域。这些区域之一将是无限的。

有限区域：如果区域的面积是有限的, 则该区域称为有限区域。

无限区域：如果区域的面积是无限的, 则该区域称为无限区域。平面图只有一个无限区域。

示例：考虑图所示。确定区域, 有限区域和无限区域的数量。

解决方案：上图中有五个区域, 即r1, r2, r3, r4, r5。

图中有四个有限区域, 即r2, r3, r4, r5。

只有一个有限区域, 即r1

平面图的性质

1. 如果连接的平面图G具有e个边缘和r个区域, 则r≤e。
2. 如果连接的平面图G具有e个边, v个顶点和r个区域, 则v-e + r = 2。
3. 如果连接的平面图G具有e个边和v个顶点, 则3v-e≥6。
4. 当且仅当n <5时, 完整图Kn才是平面。
5. 当且仅当m 3或n 3时, 一个完整的二部图Kmn是平面的。

示例：证明完整的图K4是平面的。

解决方案：完整的图K4包含4个顶点和6个边。

我们知道对于一个连通平面图3v-e≥6, 因此对于K4, 我们有3×4-6 = 6, 它满足属性（3）。

因此, K4是平面图。因此证明。

非平面图

如果无法在平面中绘制图形, 则该图形将被认为是非平面的, 这样就不会有边缘交叉。

示例：图中所示的图是非平面图。

这些图不能在平面上绘制, 因此没有边交叉, 因此它们是非平面图。

非平面图的性质

当且仅当它包含与K5或K3, 3同胚的子图时, 该图才是非平面的

例1：证明K5是非平面的。

解决方案：完整的图K5包含5个顶点和10个边。

现在, 对于连接的平面图3v-e≥6。

因此, 对于K5, 我们有3 x 5-10 = 5（这不满足属性3, 因为它必须大于或等于6）。

因此, K5是非平面图。

示例2：通过找到与K5或K3, 3同胚的子图, 来表明图中所示的图是非平面的。

解决方案：如果我们删除图G1的边（V1, V4）, （V3, V4）和（V5, V4）, 则变为K5同胚, 因此它是非平面的。

如果我们去掉边V2, V7）, 则图G2对K3, 3同胚, 因此它是非平面的。

图形着色

假设G =（V, E）是没有多个边的图。 G的顶点着色是G的顶点的颜色分配, 以便相邻的顶点具有不同的颜色。如果存在使用M-Colors的G着色, 则图G是M-Colorable。

正确的着色：如果相邻的两个顶点u和v具有不同的颜色, 则着色是正确的, 否则称为不正确的着色。

示例：考虑以下图形, 颜色C = {r, w, b, y}。使用所有颜色或更少的颜色正确地为图形着色。

图中显示的图形是最小的3色, 因此x（G）= 3

解决方案：图中显示了用所有四种颜色正确着色的图形。

图显示了用三种颜色正确着色的图形。

G的色数：产生图形G适当着色所需的最少颜色数称为G的色数, 并由x（G）表示。

示例：Kn的色数为n。

解决方案：通过为每个顶点分配不同的颜色, 可以使用n种颜色构造Kn的着色。不能给两个顶点分配相同的颜色, 因为此图形的每两个顶点相邻。因此, 色数Kn ＝ n。

图形着色的应用

图形着色的一些应用包括：

• 注册分配
• 地图着色
• 二部图检查
• 移动无线电频率指配
• 制作时间表等

陈述并证明握手定理。

握手定理：图形G中所有顶点的度数之和等于图形中边数的两倍。

从数学上讲, 它可以表示为：

∑v∈Vdeg（v）= 2e

证明：令G =（V, E）是其中V = {v1, v2, 。 。 。 。 。 。 。 。 。 。}是一组顶点, 并且E = {e1, e2。 。 。 。 。 。 。 。 。 。}是一组边。我们知道每个边都位于两个顶点之间, 因此它为每个顶点提供了一级。因此, 每个边对图的贡献度为二。因此, 所有顶点的度数之和等于G中边的数量的两倍。

因此, ∑v∈Vdeg（v）= 2e