平面图的欧拉定理

平面图

平面图是一张无向图，顾名思义：存在一种在平面上画点的方法，使得所有的边不会相交。

欧拉定理

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

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

下面是一个例子：

Snipaste_2021-01-07_14-31-51.png

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

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

即 \(C=|V|-|E|+|F|-1\)。

欧拉定理与网格图

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

Snipaste_2021-01-07_14-35-46.png

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

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

2. \(|E|\)为相邻对数

3. \(|V|\)为染色个数

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

作为一种可能出现的思路