几何学中的欧拉公式:V-E+F = 2

几何学中的欧拉公式:V-E+F = 2,V、E、F表示简单几何体的顶点数、边数、面数。

证明:

它的证明有多种,这里呈现一种递归证法。

对于任意简单几何体(几何体的边界不是曲线),我们考察这个几何体的每个面,设这个边成一个n边形,我们从某个固定顶点开始连接其其他各个顶点,即将这个n边形从某个顶点进行了三角剖分,我们假想每个三角形是一个面(因为实际上多个三角形共面),那么能够看到,这个过程中E和F的增量是相同的,因此如果原来的几何体满足V-E+F = 2,则现在这个几何体(视每个三角形为一个面)仍然满足欧拉公式。

我们随机去掉一个面,则剖分后的几何体应满足V-E+F = 1.

现在我们考察这个去掉一个面之后被三角形剖分的几何体,对于某个三角形,考察它的三个边(每条边都是被两个三角形共享),会有如下的三种情况:

(1)一个边所在的另一个三角形的那个面是空的。

(2)两个边所在的另一个三角形的那个面是空的。

(3)三个边所在的另一个三角形的那个面是空的。

那么下面我们开始一个“掏空过程”,为了分析的方便,我们不在一片没有被“掏空”的区域的内部去“掏空”某个三角形,直到最终剩余一个三角形,即我们避免了第三种情况。

面临情况(1),我们掏空这个三角形,发现边数、面数各减1,V-E+F的值将不发生变化。

面临情况(2),我们掏空这个三角形,我们发现会出现两种情况,分为顶点数减1和不变的情况(想象一下),我们非常喜欢前面这种情况,因为这使得边数减2、顶点减1、面数减1,这会使得V-E+F不变,这十分有利于我们继续进行递归的等价转化。

那么如何应对这种情况呢?还记得我们一开始随机掏空的那个三角形么,容易看到它必然由三个三角形围起来,即分享这个被掏空的三角形的三个边的三角形,我们标号为1、2、3,而这三个三角形中间势必会夹着三个三角形,我们记为4、5、6,我们采取的策略是先掏空1、2、3,然后掏空4、5、6,这样将会保证V-E+F不变,同时我们将1、2、3、4、5、6视为第一层“堡垒”,对于第二层,想一想,是否也是相同的状况(掏空4、5、6又会得到三个情况(1)中的三角形)?这就保证了我们递归的正确性。(这里不需要考虑三角形个数余6的结果,因为这种自上而下的“掏空过程”将会杜绝情况(2)的第二种情况)

那么让我们来看看递归的最终状态,对于一个三角形,V = 3 、 F  =1  、 E = 3 ,显然有V-E+F = 1,然后回溯到先前的所有状态,可知对于任意的简单几何体,有欧拉公式成立:

V-E+F = 2.

证毕。

补充:笔者今天复习离散刚好看到了该欧拉公式在平面图中的推广形式,在这里做出补充。

通常有资料认为将几何体直接映射到平面上即可完成等价转化,但个人认为这并不严谨,主要针对弧线。

定理:设G为任意的连通的平面图,则v-e+f=2,v是G的顶点数,e是G的边数,f是G的面数。

证明:其实有点类似几何学中的欧拉公式的证明方法,这里采用归纳证明的方法。

对m进行归纳,当m = 0,显然成立。

假设边数e' = e-1时成立,即有v'-e'+f'=2.考察参数为v、e、f的G图,如果存在悬挂点v1,去掉v1,则有e' = e - 1,f=f',v' = v - 1,带入之前的假设,整理得:

v-e+f=2.

而如果G中没有悬挂点,我们去掉回路中的某个边,采取类似的思路,同样可以整理出欧拉公式。

证毕。

上一篇:一次发现underscore源码bug的经历以及对学术界『拿来主义』的思考


下一篇:你的leader还在考核你的千行代码Bug率吗?