平面图的欧拉定理

平面图的欧拉定理

平面图

平面图是一张无向图，顾名思义

存在一种在平面上画点的方法，使得所有的边不会相交

欧拉定理

对于一张平面图(G=(V,E))，(F)为平面图上的边把平面划分的区域个数（注意统计最外层的无限区域），则

一张平面图是连通的 (Longleftrightarrow) (|V|-|E|+|F|=2)

下面是一个例子

(|V|=5,|E|=8,F=5) (包含最外层的区域)

很显然这个定理也可以用来统计联通块的数量/区域的数量

欧拉定理与网格图

当题目涉及到网格图染色问题时，不妨将所有染色的网格视为点，边即为四联通

此时构成一个特殊的平面图，且此时可以发现

(F)为 4相邻块个数 + 空腔个数 + 1

(|E|)为相邻对数

(|V|)为染色个数

由此可以在染色问题上把 空腔数量 与 连通性结合起来

作为一种可能出现的思路