用图的对偶性证明欧拉公式

摘要

30 秒看懂

3Blue1Brown 先解释环、生成树和平面图的对偶，再利用它们之间的关系证明连通平面图的欧拉公式。关键在于，原图生成树之外的边在对偶图中构成另一棵生成树。

1欧拉示性数对于连通平面图，把外部区域计入面数，就有 V − E + F = 2。
2生成树生成树无环地连接所有顶点，共有 V − 1 条边。
3对偶图把面视为顶点，在原图每条边的两侧连接对应的面。
4互补的树不属于原图生成树的边在对偶图中构成一棵生成树。
5统计边数两棵树分别有 V − 1 和 F − 1 条边，因此 E = V + F − 2。

要点建议

对于连通平面图，顶点数减去边数再加上面数等于二；面数包括无界的外部区域。
生成树连接所有顶点，且不含环。
对偶图的每个顶点对应原图嵌入的一个面，每条边对应跨过的一条原图边。
原图生成树之外的边构成对偶图的生成树，两棵树的边数之和导出欧拉公式。

主题Mathematics Science Communication

全文

按章节阅读整理后的全文

对照原始文稿

只看原始文稿

欧拉公式与图论术语

公式联系连通平面图的顶点、边和面。环和生成树为证明提供工具。

我想介绍一种欧拉示性数公式的证明，展示对偶性的优美。这并不是说它比通常的归纳证明更好，而是展示换一个视角如何揭示结构。

在平面上画出一个连通图，使边不相交。统计顶点数 V、边数 E，以及这些边将平面分成的面数 F，别忘记无界的外部区域。欧拉公式说 V − E + F = 2。这些术语源于欧拉最初对三维多面体的研究。

想象一个叫 Randolph 的小家伙沿图的边行走。路径是一串可供他行走、不会立即沿同一条边折返的边；环则是一条回到起点的路径。环在这里很重要，因为它们会围住一些面。

假设 Randolph 想抵达每个顶点，但只有当一条边能让他到达此前无法到达的顶点时才买下它。最后他得到一组连通且无环的边，也就是一棵树。覆盖原图所有顶点的树称为生成树。

构造对偶图

图是对象及其连接关系的抽象集合。平面嵌入的面可以成为对偶图的顶点。

图本身比画出来的图形更抽象：它由对象及其连接关系组成。账户与好友关系构成图，只差一个字母的单词之间的关系、合写过论文的数学家之间的关系也可以构成图。点和线只是描绘这些关系的一种方式。

对于一个平面图，把每个面视作对象，并把一条边两侧的面视为相连，就得到对偶图。画对偶图时，在每个面内放一个顶点，再跨过原图的边连接这些顶点。外部区域也有一个顶点，可以想象它在无穷远处；对偶图可能出现重边或自环。

区分图和图的画法，有助于理解这种对应：每条原图边都有一条对应的对偶边，即使画出来的线看起来不同。一张图中的环与分隔，和另一张图的连通性有联系。

两棵生成树与边数

生成树之外的边构成对偶图的一棵生成树。统计两棵树的边即可证明欧拉公式。

再设想 Randolph 有一个名叫 Mortimer 的另一个身份，他在对偶图中穿行于各个面之间。Randolph 拥有一棵生成树的边，Mortimer 只能跨越剩下的边。这些剩余边在对偶图中构成一棵生成树：它们连接所有面，而且没有对偶环。

为什么 Mortimer 可以到达每个面？Randolph 的边只有形成环才能将某个面围住，而树没有环。反过来，如果 Mortimer 能沿对偶图走出一个环，就会把原图的某些顶点与其他顶点隔开，这与 Randolph 的树连接所有顶点相矛盾。

幻灯片 3 / 4对偶环会隔开顶点图示说明为什么 Mortimer 可走的环会妨碍原图生成树连接所有顶点。

一棵有 V 个顶点的树有 V − 1 条边：从第一个顶点开始，每添一条边就带来一个新顶点。因此 Randolph 的树有 V − 1 条边。Mortimer 的树覆盖原图的 F 个面，所以使用余下的 F − 1 条边。两者合起来覆盖原图所有边：E = (V − 1) + (F − 1)，即 V − E + F = 2。