文章浏览阅读99次。P3209 [HNOI2010]平面图判定题目：若能将无向图 $G=(V, E)$画在平面上使得任意两条无重合顶点的边不相交，则称 $G$是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。思路：1.2-sat关于平面图有一个性质，边数一定小于等于 $3n-6$ 。所以我们对于边数大...