来自天书的证明(一):欧拉公式,平面与球面的一一对应以及共轭点-圆变换

本文遵守首页上的CC版权声明,转载请注明作者与出处,谢谢!

作者:fwjmath

题记:最近在图书馆借了一本《Proofs From THE BOOK》,里边收集了很多数学问题的有趣巧妙的证明。"THE BOOK" (天书)这个说法是著名数学家Erdos, Paul提出的,他说SF(Supreme Fascist,Erdos就是这样称呼上帝同志的)有一本超穷的天书,里边记载了所有最巧妙的数学证明。但其实Erdos本人就以巧妙的证明而闻名,更加多的关于他的趣事可以参见哲人石丛书中的《数字情种》一书。现在我就把我看到的一些有趣的证明与大家分享一下。

 

首先我们来复习一下关于平面图的欧拉公式:

欧拉公式(Euler’s Formula):
设G是一个有v个顶点、e条边和f个面(图外部计入一个面)的连通平面图,那么我们有:
v-e+f=2
 
这个公式的证明在图论书上都有,基本上都是使用归纳法的。现在在这里介绍一个不需要归纳证明的漂亮方法。
 
证明:设G(V,E)为平面图。定义它的对偶图为G*(V*,E*),构造方法如下:V*中的每一个顶点对应G中的一个面,而E*中的每一条边对应G中两个面的公共边,注意外部也算作一个面。图示如下:

dualgraph

其中红色为G蓝色为G*。

但其实这种说明是不必要的,因为从图中我们可以看出这两个图是互为对偶的。

考虑E的一棵生成树Tree(V,T),令E*的子集T*为那些对应ET中的图G中的边的图G*中的边。构造图Tree*(V*,T*)。这样的话Tree*是连通的,因为T中无圈。类似地,根据两个图互为对偶的性质,稍微用一下反证法,我们可以得到Tree*也是无圈的。所以Tree*也是G*的一棵生成树。上图粗线部分就是这样两棵树的例子。

我们知道,对于一棵树来说,它的顶点数等于它的边数加一。分别对Tree和Tree*应用这个结论,我们得到:|V|=|T|+1,|V*|=|T*|+1。但我们又有|V|=v,|V*|=f(因为G*中每个顶点对应G中的一个面),|T*|+|T|=|ET|+|T|=e。这样,将头两个式子相加并利用后面的式子化简,我们立刻得到v+f=e+2。证毕。

欧拉公式虽然其貌不扬,但是却可以用来证明很多东西,比如说两个著名的不可平面图K5和K(3,3)的不可平面性的证明。

 

定理:K5与K(3,3)为不可平面图。

证明:如果K5是平面图的话,考虑它的一个平面展开。对应的v=5, e=10, f=e+2-v=7。但这样的话每个面的边数的平均值~f=2e/f=20/7<3,至少存在一个面只有两条边,这是不可能的。

如果K(3,3)是平面图的话,考虑它的一个平面展开。对应的v=6, e=9, f=e+2-v=5。但这样的话每个面的边数的平均值~f=2e/f=18/5<4,由于K(3,3)是二部图,面的边数是偶数,所以至少存在一个面只有两条边,这是不可能的。

综上,知K5与K(3,3)为不可平面图。证毕。

 

这个证明在绝大多数的图论教材里边都应该有讲到。

下面再用欧拉公式来证明两个不平凡的结论,其中利用了算两次的想法。

 

命题:设G是一个非空简单连通平面图。我们有:

(A) G中存在一个顶点,这个顶点的度不超过5。

(B) 如果我们将G的每条边染二色,那么G中存在一个顶点,我们在环状访问它连出去的边的时候至多碰到两次颜色改变。

证明:首先我们约定一些记号。f(n)表示有n个顶点的面的个数,v(n)表示度数为n的点的个数。

(A) 由于G是简单图,所以每个面至少有三条边。这样的话我们有:

f = f(3) + f(4) + f(5) + …

2e = 3f(3) + 4f(4) + 5f(5) + …

于是我们有 2e – 3f >= 0。

用反证法。如果每个顶点的度数都大于等于6的话,我们有:

v = v(6) + v(7) + v(8) + …

2e = 6f(6) + 7f(7) + 8f(8) + …

于是我们有 2e – 6v >= 0。

两个不等式相加,我们可以得到:(2e – 6v) + 2(2e – 3f) >= 0,于是 6(e – v – f) >= 0, e >= v + f,与欧拉公式矛盾!

所以至少存在一个度数小于等于5的顶点。证毕。

(B) 用反证法,设每个顶点连出去的边的颜色转换次数至少是4(因为环状访问,所以颜色转换次数必定为偶数)。令c为每个顶点连出去的边的颜色转换次数的和。

然后我们看每个面的情况。容易知道,如果我们环状访问每个面,它们的边的颜色转换次数总和正好等于c(考虑同一个顶点伸出的两条相邻的边,c可以考虑成颜色不同的一对这样的边的总数,分别针对顶点和针对面求和就可以知道)。由于是环状访问,我们知道每个面的边的颜色转换次数是一个偶数。这样的话,对于一个有2k或者2k+1个顶点的面来说这样的转换最多有2k次。这样的话我们就得到以下两个不等式:

4e – 4f = 2(3f(3) + 4f(4) + 5f(5) + 6f(6) + 7f(7) + …) – 4(f(3) + f(4) + f(5) + f(6) + f(7)+…)
           = 2f(3) + 4f(4) + 6f(5) + 8f(6) + 10f(7) + …
         >= 2f(3) + 4f(4) + 4f(5) + 6f(6) + 6f(7) + …
         >= c

以及 c >= 4n。

结合两式,我们得到 4e – 4f >= 4n, e >= n + f,这与欧拉公式矛盾。

所以必定存在颜色转换次数小于等于2的顶点。证毕。

 

欧拉公式除了在平面上适用以外,在球面上也适用。这个的证明很简单。对于一个球面上的图来说,我们可以将其进行拓扑变换,使得所有顶点和边都处于一个半球上。然后我们以球心为中心,将半球上的顶点和边都投影到一个平行于赤道所在平面的切半球面的平面上,容易知道这是一个一一对应。这样我们就建立了平面图和球面图的一个一一对应关系。容易知道欧拉公式对于球面图也适用。同样地,上面的命题对于球面图也适用。

平面上和球面上的欧拉公式的常数是一样的,这是否意味着什么呢?其实,在拓扑学上来说,从某种意义上来说平面和球面是等价的,可以互相转化。它们的所谓“欧拉示性数”都是2,因为它们的亏格都是0。不过这些东西在我们随后的证明中是不需要的。我们只需要知道平面和球面上的图可以一一对应就可以了。

准备知识已经充足了,下面我们就来看两个很有趣的定理的很简单的证明。

 

Sylvester-Gallai 定理:给定平面上一个点数大于等于3的不全共线的点集,则必存在一条直线恰好通过两点。

证明:取平面以外的一个球面,将平面上点集的点与直线与球面的点和大圆(半径等于球半径的圆)进行一一对应,具体方法是联结平面上一点和球心的直线交球面于两点(容易知道这两点就是所谓的对蹬点),这两点就是平面上点的对应点。容易知道平面上直线的对应就是球面上的大圆。进行这样的对应之后,我们就得到一个经过变换的要证明的命题:

对于球面上任意元素个数大于等于3的对蹬点对集,如果它们都不在同一个大圆上的话,必定存在一个大圆恰好通过两对对蹬点。

然后我们构造这个对蹬点集的对偶大圆集。对于每对对蹬点,我们取过球心的垂直于两点连线的平面与球面相交的那个大圆,如图:

conjugate_great_circle

这样的话只需要证明:

对于任意个数大于等于3的不全共点的球面大圆集,必存在一点恰好是两个大圆的交点。

如果我们以大圆交点为顶点,大圆上的弧为边的话,我们可以得到一幅球面图。而且这个球面图还是简单图,否则存在一个面只由两条边组成的话,两个顶点必定是对蹬点,这样的话由于大圆不全共点,必存在一个不包含两条边的大圆交这两条边,这是不可能的,所以这个球面图是简单图。容易知道,这个图每个顶点的度数都是偶数(因为是大圆交点)。根据命题的(A)部分,我们知道存在一个度数小于等于5的顶点,也就是说这个球面图上存在一个度数小于等于4的顶点。又因为顶点度数至少为4(顶点是至少两个大圆的交点),这样的话必存在一点度数为4,也就是说是恰好两个大圆的交点。命题证毕,于是原命题也是正确的。证毕。

 

Don Chakerian 定理:平面上给定任意有穷不全共线点集(点数大于等于3),将其染黑白二色,则必存在一条直线通过的点至少有两个而且颜色都相同。

证明:用类似 Sylvester-Gallai 定理证明中的方法,我们将平面点集投影到球面上,再构造对偶的大圆集,我们可以得到对应的要证明的命题:

球面上给定任意有穷不全共点的大圆集合,将其染黑白二色,则必存在一个大圆的交点是仅由同一种颜色的大圆相交而成的。

类似上面证明,我们考虑以大圆交点为顶点、大圆上的弧为边的球面图。这个球面图也是简单图。根据命题的(B)部分,存在一个顶点的颜色转换数少于等于2。然而在这个球面图上,如果一个点由两种颜色的大圆相交而成的话颜色转换数至少是4,所以必定存在一点仅由一种颜色的大圆相交而成。命题证毕,于是原命题也是正确的。证毕。

 

这就是欧拉公式的几个应用。

Advertisements

One thought on “来自天书的证明(一):欧拉公式,平面与球面的一一对应以及共轭点-圆变换

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s