From faccc94f7f1f5cc0b41de8f4d142f7871c76e5de Mon Sep 17 00:00:00 2001 From: frank <34837108+frank-xjh@users.noreply.github.com> Date: Sun, 2 Sep 2018 18:48:17 +0800 Subject: [PATCH] Update 2-sat.md --- docs/graph/2-sat.md | 1 + 1 file changed, 1 insertion(+) diff --git a/docs/graph/2-sat.md b/docs/graph/2-sat.md index aa0cc7ec..cd9f4670 100644 --- a/docs/graph/2-sat.md +++ b/docs/graph/2-sat.md @@ -1,4 +1,5 @@ > SAT 是适定性( Satisfiability )问题的简称 。一般形式为k-适定性问题,简称 k-SAT 。而当 $k>2$ 时该问题为 NP 完全的。所以我们之研究 $k=2$ 的情况。 + ## 定义 2-SAT ,简单的说就是给出 n 个集合,每个集合有两个元素,已知若干个 ,表示 a 与 b 矛盾(其中a与b属于不同的集合)。 然后从每个集合选择一个元素,判断能否一共选 n 个两两不矛盾的元素。显然可能有多种选择方案,一般题中只需要求出一种即可。 -- 2.11.0