平面图欧拉公式

大家都知道关于平面图的欧拉公式为 V – E + F = 2，我想讨论一些关于欧拉公式的证明及应用。首先欧拉公式用于平面图的标准形式为 V – E + F = C + 1,其中 V 为顶点数，E 为边数，F 为面数（包括图边界以外的面），C 为连通数。

我没有了解过关于欧拉公式的严格证明，但在这里给出一个能够自圆其说且比较通俗易懂的证明（C = 1）。首先所有平面图都可以通过添加点和添加边来得到，也可以通过删边和删点来删除。当我们向一个图中添加一个点时，一定要添加一条边，否则添加点后的图不连通。易得 V + 1，E + 1 不会改变欧拉公式的正确性。如果向原图添加一条边，可得我们会多得到一个面，从而也不改变欧拉公式的正确性。又由于欧拉公式对于一个点来说是正确的，所以它对于所有平面图成立。我希望大家能充分展开对平面图例子的想象，从而得到一些关于欧拉公式的特殊形式比如树也是平面图，所以欧拉公式对树来说就变成了 V = E + 1，对于不连通的图我们有 V – E + F = C + 1。在特殊的图中往往可以得到 V,E,F三者之间某2者的关系从而将欧拉公式简化。让我们来看一下欧拉公式在平面分割中的应用：

将右图转化为下图，图中A,B,C,D,E,F作为无穷远点，此图满足欧拉公式 9 – 9 + 2 = 2，由于在直线分割平面的问题中求的是F，由无穷远点所分割的面数为6。所以公式就演变为（顶点个数）- （边数）+ F = 2 + （无穷远点个数）- 1。下面“佐罗的烦恼”同样可以用这样的方法推得欧拉公式的特殊形式。

---