资源描述：
《信息学奥林匹克论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、信息学奥林匹克论文华中师大一附中赵爽1/32-SAT解法浅析华中师大一附中赵爽SAT理论基础设Bb={,,b?,b}为一个有限布尔变量集，Bˆ=¬{bb,,??,b,b,¬b,,¬b}。12n12nn12设B′是Bˆ的非空子集，定义∨=B′∨b。对于给定的BB′′,,?,B′∈Bˆ①，求B，使得12mbB∈′()∨∧BB′′(∨)∧?∧(∨B′)=112m成立的问题，称为适定性(Satisfiability)问题，简称SAT。特别的，对于给定的{B′}，如果max{B′}=k，我们就把这个问题称为k-适定性miim=1,2,?,问题，简称k-SAT。可以证明，当
2、k>2时，k-SAT是NP完全的。下面我们要讨论的，是k=2时的情况。2-SAT在2-SAT中，B′只有两种形式，一种是单个布尔变量x∈Bˆ，另一种是两个布尔变量i的或：x∨yx(,y∈Bˆ)。为了方便，我们先分析只存在后一种形式的情况。我们可以构造有向图G。G包含2n个顶点，代表Bˆ中的2n个元素。我们的问题转化为从G中选出n个顶点，使其满足2-SAT的条件——当然，代表b和¬b的顶点不能同时ii被选择。下面我们分析一下B′=∨xy在图对应什么。i显然，x∨=y¬(¬x∧¬y)。这也就是说，如果我们选中¬x，那么我们必须选择y；同样的，如果我们选中¬y，那么我
3、们必须选择x。因此，对于B′=x∨y，我们可以在Gi②中增加弧()¬x,y和(¬yx,)。①在下文中，X,,?X简写作{X}。1nn②这里，x,,yx¬¬,y都表示G中代表它们的顶点。下同。信息学奥林匹克论文华中师大一附中赵爽2/3然后我们可以求G的所有强连通分量。很明显，如果我们选中强连通分量中的任何一点，那么该强连通分量中的所有其它的顶点也必须被选择。如果b和¬b同属于一个强连jj通分量，那么产生矛盾，该2-SAT无解。如果没有产生矛盾，我们就可以把处在同一个强连通分量中的点和边缩成一个点，得到新的有向图G′。然后，我们把G′中的所有弧反向，得到图G′′。现
4、在我们观察G′′。由于已经进行了缩点的操作，因此G′′中一定不存在圈，也就是说，G′′具有拓扑结构。我们把G′′中所有顶点置为“未着色”。按照拓扑顺序重复下面的操作：1、选择第一个未着色的顶点x。把x染成红色。2、把所有与x矛盾的顶点y（如果存在bb,¬∈Bˆ，且b属于x代表的强连jjj通分量，¬b属于y代表的强连通分量，那么x和y就是互相矛盾的顶点）j及其子孙全部全部染成蓝色。3、重复操作1和2，直到不存在未着色的点为止。此时，G′′中被染成红色的点在图G中对应的顶点集合，就对应着该2-SAT的一组解。那么，以上的操作中是否可能出现矛盾呢？答案是否定的。这是因
5、为：首先，假如我们选定了G′′中的未着色顶点p，那么和p矛盾的所有其它顶点及其后代均会被染成蓝色。因此，我们把一个顶点p染成红色时，任何一个和p矛盾顶点都不会也是红色。同时，由于我们按照拓扑顺序检查，并且把一个顶点染成蓝色的时候，立刻把它的所有子孙也染成蓝色。也就是说，如果一个顶点p不可选，那么所有直接或间接满足条件“假如选择q就必须选择p”的顶点也会被染成蓝色。这样一来，G′′中不存在弧(x,y)，其中x为红色而y为蓝色。因此我们得到的结论不可能和B′对应的条件矛盾。i综合这两条结论，我们就可能证明上面的操作中不会产生任何矛盾。下面证明G′′对应的解就是该2-
6、SAT的解，即：1、我们得到的解不会同时选定b和¬b。jj证明：首先，对于b和¬b，它们在G中一定属于不同的强连通分量（如果不满足这个条jj件，事先就会被判定为无解），因此在G′′中被不同的顶点所代表，不妨设为p和q。显然p和q是相互矛盾的顶点。由于上面的着色操作不会产生矛盾（已证），因此p和q不会被同时染成红色，即不可能同时选定b和¬b。证毕。jj2、我们得到的解对于任意的bb,¬∈Bˆ，会至少包含其中的一个。jj证明：注意到对于G中任何一条弧(x,y)，一定存在一条与之“对偶”的弧()¬¬y,x。这信息学奥林匹克论文华中师大一附中赵爽3/3是由B′的形式决定
7、的。这就意味着如果x,y处于G的同一个强连通分量内，那么i¬x,¬y必然也处于同一个强连通分量内；如果x,y之间有路，那么¬y,¬x之间也有路。假设b,¬b均未被选中，即它们所在的强连通分量p,q均被染成蓝色。下面分两种情jj况进行讨论：(1)p,q是在同一次染色操作中被染成蓝色不妨假设把顶点r染成红色之后，将p,q同时染成蓝色。在G′′中，p,q之间不存在路径。因为如果p,q之间有路，那么由G的结构可知q,p之间也有路，这和G′′的拓扑结构矛盾。如果p,q之间没有路，那么一定存在p′,q′∈G′′，它们和r直接矛盾，且p③是p′的后代，q是q′的后代。即存在G
8、x()∈¬G′′′(r)
