Contest

笔记

欧拉定理

• 欧拉定理
  • 连通平面图满足 $V - E + F = 2$。
  • 有 $C$ 个连通块的平面图满足 $V - E + F = C + 1$。
• 简单连通平面图满足 $E \le 3V - 6$。
  • 重要：平面图满足 $E = O(V)$。
  • 可以用于证明 $K_5$ 不是平面图。
• 一个 $V \ge 3$ 的简单连通平面图，如果它不含有 $K_3$（三元环），那么 $E \le 2V-4$。
  • 可以用于证明 $K_{3,3}$ 不是平面图。

图同胚

• 图的同胚操作：（能通过同胚操作转换成同构图的两张图称为同胚的两张图）
  • 切割（Wiki 上称其为细分变换）：把边 $A \leftrightarrow C$ 更改为 $A \leftrightarrow B \leftrightarrow C$。
  • 节点贯通（Wiki 上称其为平滑变换）：对于一个度数为 $2$ 的点 $B$，把 $A \leftrightarrow B \leftrightarrow C$ 更改为 $A \leftrightarrow C$。
• Kuratowski’s theorem：一张图是平面图的充要条件是不存在子图同胚于 $K_5$ 或 $K_{3,3}$。
  • 推论：一张图不是平面图的充要条件是存在子图同胚于 $K_5$ 或 $K_{3,3}$。

对偶图

严谨定义不想写了，放一张 Wiki 上的图：

其中蓝图为原图，红图为其对偶图（dual graph）。

• 连通平面图的对偶图是连通平面图。
• 同构图的对偶图不一定同构。
• 平面图最大流 = 平面图最小割 = 对偶图最短路。
  • $S \rightarrow T$ 的最大流，可以多连一条边 $S \leftrightarrow T$，这条边会把无限面分为两半 $S^$ 和 $T^$，在对偶图上做 $S^* \rightarrow T^*$ 的最短路即可。

A 平面图判定

P3209 [HNOI2010] 平面图判定

B 防鼠工程

P4001 [ICPC-Beijing 2006] 狼抓兔子

平面图最小割 = 对偶图最短路 板子。虽然 Dinic 能过

C 团购

P10665 [AMPPZ2013] Bytehattan 好新的题

TODO: Still Working on it!

D 海拔

P2046 [NOI2010] 海拔

注意到「存在至少一组最优方案使得每个交叉路口海拔都为 $0$ 或 $1$，且海拔都为 $0$ 和 $1$ 的交叉路口分别仅构成一个极大四连通块」。证明比较困难，见洛谷题解区第一篇 TODO: Still Working on it!

然后直接按 B 题做就行了。