平面图欧拉公式

· · 算法·理论

公式内容：V-E+F=1+C，其中 V 是点数，E 是边数，F 是面数，C 是连通块数。

定理 对于平面图 G=(V,E)，设其对偶图为 G^*=(V^*,E^*)，C 表示 G 的连通块数，则 |V|-|E|+|V^*|=1+C。

平面图与对偶图相关可以去 OI-Wiki 学习。

一个简单的证明方法是归纳，每次删掉一个小犄♂角，欧拉公式仍成立，直到只剩若干三角形。本文通过对偶图和生成树证明。

证明 记 E^* 表示 E 中的所有边在对偶图 G^* 中对应的边构成的集合。

引理 取 G 的一棵生成树 T=(V,E_1)，记 E_2=E\backslash E_1，那么 G^* 的子图 T^*=(V^*,E_2^*) 也是一棵树。

证明 先证明 T^* 连通。由于 T 无环，则每个面都可通过 e\in E_2 走到另一个面（若不行，找一块连通的面，那么环绕着该连通块的 E_1 中的边显然成环了，与 T 是树矛盾），即 T^* 中所有点连通。

再证明 T^* 无环。和上面类似，有环代表一坨面包围了 T 的子图使其不与外界连通，与 T 是树矛盾。因此 T^* 无环。

综上，T^* 也是一棵树。

\square

先考虑 G 连通的情况，此时 C=1，就是我们最熟悉的平面图欧拉公式。

取出 G 的生成树 T=(V,E_1)，记 E_2=E\backslash E_1,T^*=(V^*,E_2^*)。由引理得 T^* 也是一棵树。

已知 E_1+E_2=E,|E_2^*|=|E_2|，因此 |V|-|E|+|V^*|=(|V|-|E_1|)+(|V^*|-|E_2^*|)=2。这样原图连通的情况就证完了。

对于 G 存在若干连通块的情况也类似，只不过需要把 |V|-|E_1| 拆成 \sum_{G'\ {\sf 是}\ G\ {\sf 的极大连通子图}}|V(G')|-|E(G')|。每个连通块贡献 1（树的点比边多 1），因此 |V|-|E|+|V^*|=1+C。

\square

拓展：三维几何体中那个欧拉公式可以通过挖掉一个面再拍扁转化成平面图证明。

CF933C 是一个简单的例题，快去练练手吧！