~/posts/planar-gpraph.md

更多图论

2026-02-24 12 分钟 · 5597 字12 min · 5597 words mathematics mathematics
目录Contents

上次我们谈到当时,完全图不是平面图。现在我们将致力于证明这一点。

一些概念

  • 平面图(planar graph):如果一个图可以被绘制在平面上,并且其边仅在顶点处相交,那么这个图就是平面图。
  • 完全图(complete graph):一个完全图是一个简单图,其中每对不同的顶点之间都恰好有一条边。
  • 二分图(bipartite graph):一个二分图是一个图,其顶点集合可以被划分为两个不相交的子集和,使得图中的每条边都连接一个来自的顶点和一个来自的顶点。
  • 面(faces):在平面图中,边界由边和顶点组成的区域被称为面(face)。每个面都是一个闭合的区域,可以是有限的也可以是无限的。

根据上面的定义,二分图是指其顶点集合可以被划分为两个不相交的子集和,使得图中的每条边都连接一个来自的顶点和一个来自的顶点。换句话说,在二分图中不存在连接同一子集内两个顶点的边。例如,考虑下面的图:

text
       A
      / \
     B   C
      \ /
       D

在这个图中,我们可以将顶点集合划分为和,使得每条边都连接一个来自的顶点和一个来自的顶点。因此,这个图是一个二分图,我们可以将其称为,因为它是一个完全二分图,其中和分别有两个顶点。显然,是一个平面图,因为我们可以在平面上绘制它而不使边相交。那么呢?是一个完全二分图,其中和分别有三个顶点。我们可以尝试在平面上绘制,但是无论我们如何尝试,我们都会发现至少有两条边相交。我们有理由相信,不是一个平面图。下面,我们也将证明这一点。

欧拉公式(Euler’s formula)

对于一个连通的平面图,欧拉公式表明顶点数、边数和面数之间满足以下关系:

这个公式是由瑞士数学家莱昂哈德·欧拉在18世纪提出的。它揭示了平面图的基本结构,并且在证明平面图的一些性质时非常有用。 至于如何证明,此处先略去不谈。

证明不是平面图

假设是一个平面图,那么它必须满足欧拉公式。对于,我们有和。将这些值代入欧拉公式,我们得到:

因此,面数必须等于7。然而,在一个平面图中,每条边至多属于两个不同的面(因为边界必须由边和顶点组成),而每个面至少由三条边组成,所以我们有以下不等式:

将和代入这个不等式,我们得到:

这是一个矛盾,因此我们的假设是错误的。由此我们得出结论:不是一个平面图。

证明不是平面图

这个证明其实与上面类似。对于,我们有和。将这些值代入欧拉公式,我们得到:

因此,面数必须等于5。但是在这样一个二分图中,每条边至少属于两个不同的面(因为边界必须由边和顶点组成),而每个面至少由四条边组成(因为二分图中不存在连接同一子集内两个顶点的边,所以每个面至少需要四条边才能形成一个闭合区域),所以我们有以下不等式:

将和代入这个不等式,我们得到:

这是一个矛盾,因此我们的假设是错误的。由此我们得出结论:不是一个平面图。

上面的两个证明是同一个套路,即欧拉公式+边-面邻接关系从而得出矛盾。我们可以总结出一个结论:如果一个图是一个平面图,那么必须满足以下不等式:

如果是一个二分图,那么必须满足以下不等式:

一个定理

定理:一个图是一个平面图的充分必要条件是中不存在或的子图。

这个定理的一个方向已经被我们证明了,但是另一个方向却没有那么容易。这个定理被称为库拉托夫斯基定理(Kuratowski’s theorem)。其证明相当困难,这里有一个证明,得日后再研究了。

欧拉公式的证明:数学归纳法

看了上面的两个证明,可以感受到欧拉公式的威力。现在我们来证明欧拉公式。我们使用数学归纳法来证明这个结论。

  • 基础情况:当时,欧拉公式成立。
  • 归纳假设:假设对于任意一个连通的平面图,如果是一个树,根据前面树的性质,我们知道,并且(因为树只有一个面,即整个平面),所以欧拉公式成立。而如果中至少存在一个环,那么我们可以找到一个环,并且去掉这个环上的一条边,得到一个新的图。根据归纳假设,满足欧拉公式,即。
  • 归纳步骤:现在我们来分析和之间的关系。因为我们去掉了一个环上的一条边,所以。同时,去掉这条边会将环分成两个面,因此。而顶点数没有改变,所以。将这些关系代入欧拉公式,我们得到: 因此,也满足欧拉公式。通过数学归纳法,我们证明了对于任意一个连通的平面图,欧拉公式都成立。

端点染色

染色问题就是指用多少种不同的颜色给图的顶点着色,使得相邻顶点的颜色不同。实际上,任何端点染色问题都可以一一映射为一个图的着色问题。我们可以将每个端点看作一个顶点,将每条边看作连接两个顶点的边,那么端点染色问题就转化为了图的着色问题。而端点染色问题和上面提到的平面图、完全图和树等概念密切相关。我们可以用手画几张图感受一下染色的过程。

六色定理

首先,任何一张平面图,用六种颜色就一定可以完成端点染色。这个问题等价于将平面图中的所有点分成六类,使得每类中的点之间没有边相连(也可以说是一种“六分图”)。我们来证明这个论断。 假设我们有一个平面图,我们可以使用欧拉公式来分析这个图的结构。根据欧拉公式,我们知道对于一个连通的平面图,顶点数、边数和面数满足以下关系:

同时,我们还知道在一个平面图中,每条边属于两个不同的面,而每个面至少由三条边组成,所以我们有以下不等式:

将这个不等式代入欧拉公式,我们得到:

这张图的总度数是,所以平均度数是。因此,至少存在一个顶点的度数不超过5。我们可以将这个顶点染成第一种颜色,然后将与这个顶点相邻的顶点染成第二种颜色。接下来,我们可以将与第二种颜色相邻的顶点染成第三种颜色,以此类推,直到我们使用了六种颜色为止。然后,将这个点移除/忽略,继续对剩下的图进行染色。通过这种方式,我们可以确保相邻的顶点不会被染成同一种颜色,因此我们可以使用六种颜色完成端点染色。

五色定理

接下来,我们可以观察到,对于一个有五条边连接的中心点来说,如果它的其中两个不同颜色的邻居之间存在一条仅由这两种颜色的连通分量(也就是一张子图)相连,那么我们可以交换这个子图中的两种颜色,使之仍然是一个有效的染色图。也就是说,如果这样的子图中间存在断点将其分成两半,那么我们可以将其中一个邻居的那半个连通分量上的互换颜色,从而为中心点腾出一个颜色,这样我们就可以少用一种颜色来完成染色。通过这种方式,我们可以将需要的颜色数减少到五种。 接下来,我们来证明,对于一个有五条边的中心顶点来说,最差的情况是它们已经用完五种颜色了,这时需要我们通过变换其中一个邻居的颜色来为中心点腾出一种颜色。假设我们有一个中心顶点,它有五个邻居,每个邻居都被染成了不同的颜色。我们可以观察到,如果存在一个仅由两种颜色组成的连通分量连接了其中两个邻居,例如和,那么这两种颜色就无法通过交换来为中心点腾出一个颜色,因为交换后和仍然会占用两种不同的颜色。而对于和,如果它们之间同样存在一个仅由两种颜色组成的连通分量,那么交换后和仍然会占用两种不同的颜色。但同时存在两个这样的连通分量是不可能的,因为如果存在,那么根据平面图的要求,这两个连通分量之间必然相交,相交的那个点需要同时染成或的颜色和或的颜色,一个点不能染成两种颜色,因此矛盾。因此,至少存在一个邻居的颜色可以通过交换来为中心点腾出一个颜色,从而使得我们只需要五种颜色来完成染色。

超立方体

定义

超立方体(hypercube)是一个立方体,每个点代表一个由0和1组成的字符串,每条边连接两个字符串之间仅有一个位置不同的点。例如,三维超立方体(也称为立方体)有8个顶点,分别是000、001、010、011、100、101、110和111。每条边连接两个顶点,这些顶点之间仅有一个位置不同,例如000和001之间有一条边,因为它们在最后一个位置上不同;而000和110之间则没有边,因为它们有两个位置都不同。 还有一种使用递归的定义方式,任意一个维超立方体可以通过将两个维超立方体连接起来构造出来。具体来说,我们可以将一个维超立方体的每个顶点与另一个维超立方体的对应顶点连接起来,从而形成一个新的维超立方体。例如,二维超立方体(也称为正方形)可以通过连接两个一维超立方体(线段)来构造出来;三维超立方体(也称为立方体)可以通过连接两个二维超立方体(正方形)来构造出来,以此类推。此外,我们规定是一个单点图,即一个只有一个顶点和没有边的图。

性质

  • 对于:
    • 顶点数:
    • 边数:
    • 每个顶点的度数:
    • 面数:

连通性

很明显,是一个连通图,而且连通性相当强。为了描述它的连通性,我们有如下定理:

定理:对于,如果且(即),记为和之间的边的集合,即,那么。

证明:我们使用数学归纳法来证明这个定理。

  • 基础情况:当时,是一个线段图,对于其子集满足,即只能是包含一个点的集合,此时,基础情况成立。
  • 归纳假设:假设对于,定理成立,即对于任意子集,如果,则。
  • 归纳步骤:为了便于利用假设,我们将看作是由两个连接而成的图。设这两个分别为和,其中的顶点集合为,的顶点集合为。每个顶点与对应的顶点之间有一条边连接。这时,我们记 ,其中和分别是和的顶点集合。由于和的大小不确定,我们需要考虑两种情况:
    1. 如果且,根据归纳假设,我们有和。同时,由于每个顶点与对应的顶点之间有一条边连接,因此实际删去的边数不小于分别从两个集合中删去的边数,即
    2. 如果,由于,我们有。根据归纳假设,我们有。遗憾的是,我们不能直接对应用归纳假设,但是呢?很明显,因为,所以,所以我们可以对应用归纳假设,得到。同时,我们知道将个点从中删去的边数与将个点从中删去的边数相同,因为每条边连接的两个顶点分别来自和,所以我们有 但是这还不够,我们需要进一步考虑交叉边,即连接和之间的边。由于每个顶点与对应的顶点之间有一条边连接,因此至少有条边连接和,所以上面的不等式可以更加精确: 因此,在两种情况下,我们都得到了,完成了归纳步骤。

对偶图

对于一张超立方体,我们将其每个面看作一个顶点,每条边对应两个面之间的边界,那么我们就得到了的一个对偶图(dual graph)。多画几张图,我们会发现超立方体的对呕图都是平面图。对偶图的每个点度数均为,因此它不是二分图。 一般的,对于一个平面图,我们可以通过将每个面看作一个顶点,每条边对应两个面之间的边界来构造的对偶图。如果是一个平面图,那么也是一个平面图,并且满足以下关系:

  • 因此,和之间存在一种对偶关系,即中的顶点对应于中的面,中的边对应于中的边,中的面对应于中的顶点。

gitalk --repo Huaji-tye2007/MyBlog-Comments

滚动到这里时加载评论…Comments load when you scroll here…