图论杂项 ​

平面图相关 ​

平面图定义 ​

能画在平面上，边与边除端点外不相交的图。

相关概念 ​

• 无限面：即外部面。
• 有限面：即内部面。
• 面的次数：面边界的边数。

重要推论 ​

平面图所有面的次数和等于其度数的两倍。

极大平面图 ​

• 定义：多连任何一条边都不合法的图。
• 定理：一张图是极大平面图等价于其所有面次数都是 3。

欧拉公式 ​

$V - E + F = 2$，适用于平面图和多边形。

重要结论 ​

• 平面图的边数不超过 $3\times n - 6$。
  • proof：文档未给出具体证明内容。
• 平面图中至少存在一个度数不超过 5 的结点。
  • proof：反证即可。

对偶图 ​

• 定义：每个面作为结点，两个点有边等价于两个面相邻。
• 性质：
  • 平面图最小割 = 对偶图最小环。由上述引理可知，平面图最小割 <= 5。
  • 平面图 $x$ 和 $y$ 之间的最小割 = 对偶图中最小的包围 $x$ 或 $y$ 的环。在网格图中，可以将环在无限面处拆开，从而变成最短路。

偏序集相关 ​

• 传递闭包：刻画可达性的 01 矩阵。
• 偏序集：传递闭包就是其本身的 DAG。
• dilworth 引理：偏序集的最小路径覆盖 = 其最大独立集。这里的路径覆盖可以是相交或不相交。

简单应用 ​

• CSP - S 2024 决斗
• 导弹拦截 plus