问题描述 SAT(satisfiabality) 是适应性的缩写，一般称 k 的适应性问题为 k-SAT。适应性问题指有 \(n\) 个布尔变量 \(\{x_i\}\)，加入一些限制然后求限制内的解的问题。 因为 \(k>2\) 的 k-SAT 问题是 NP 完全问题（没有一定的算法和正解），我们只讨论 2-SAT 问题。 Tarjan 一般来讲，我们会想到把变量 \(x...

平面图 平面图就是所有点的连边可以在平面上不相交的图。这一点可以大概理解成拓扑图的性质，即每连一条边就会将某个区域进行分割——很明显，如果两个点分别处在两个不可达的区域，它们要连边显然是要穿过其他边的。 平面图定理 边数大于点数的三倍减六的图一定不是平面图。即设n为点数，m为边数，有 \[m<=n*3-6\] 关于平面图的其他定理和上定理的证明我不会不过我有大佬博客就不乱搬了...