【学习笔记】平面图

什么是平面图？除了节点外边没有交点的图。对于一个区域，我们称其为面；包围这个区域的边称其为边界；边界的长度称为这个面的度。

---

1. |E| <= 3|V| - 6

这告诉我们 平面图里 m 与 n 同阶。

2. V - E + F = K + 1

任何一个凸多面体（或连通平面图）满足上式，其中 F 为面数，K 为连通块数。

欧拉定理。

3. 平面图的判定：（以 [HNOI2010]-planar 为例）（其实是只会存在哈密顿回路的）哈密顿回路会连成一个环，每条边就是环上的一条弦，两条边 i 和 j 若 xi < xj < yi < yj 则相交，只能一条放环里、一条放环外——这是个二分图嘛！二分图有无合法染色等价于有无解啦。

接下来是平面图转对偶图。

4. 对于一个 s-t 平面图（有源点和汇点的平面图），其对偶图中的一个环对应着原图中的一个割。
将平面图最小割或最大流转化成对偶图最短路，效果绝佳。（但我没写过qvq）

例题：HNOI2011-平面图判定

利用哈密顿路径上的编号先后 判断边是否交，转二分图判定就好啦，并查集和 $2-sat$ 都可以