* {'Aplicaţii':2-sat#aplicatii}
** {'Party (preONI 2003/2004)':2-sat#party}
** {'Cigraf':2-sat#cigraf}

** {'Peace Commission (Polish Olympiad in Informatics, 2001)':2-sat#peace-commission}

** {'Orpath (Olimpiadă Rusia)':2-sat#orpath}
** {'Aladdin (Bursele Agora 2005/2006, Runda 1)':2-sat#aladdin}

* {'Probleme propuse':2-sat#probleme}

* {'Bibliografie':2-sat#bibliografie}
h2(#introducere). Introducere

h3. Soluţie
Dacă între două noduri există muchie atunci nu pot fi amândouă în mulţimea <tex> I </tex>, iar dacă între două noduri nu există muchie nu pot fi amândouă în mulţimea <tex> C </tex>. Transformăm această problemă într-o instanţă de $2-SAT$ astfel: faptul că nodul <tex> x </tex> aparţine mulţimii <tex> C </tex> îl reprezentăm dându-i lui <tex> x </tex> valoarea <tex> 1 </tex>, iar apartenenţa la mulţimea <tex> I </tex> se codifică prin valoarea <tex> 0 </tex>. Acum existenţa unei muchii <tex> (x, y) </tex> corespunde expresiei <tex> x \vee y </tex>, astfel cel puţin unul din nodurile <tex> x </tex> şi <tex> y </tex> nu va fi în mulţimea <tex> I </tex>. Dacă nu există muchia <tex> (x, y) </tex> putem scrie <tex> \sim x \vee \sim y </tex>, această expresie va fi adevărată dacă cel puţin un nod din cele două nu va fi în mulţimea <tex> C </tex>.

Această soluţie este liniară ca şi complexitate în numărul de elemente citite la intrare.(???)
 
h2(#peace-commission). Peace Commission (Polish Olympiad in Informatics, 2001)
 
bq. Comisia Publică a Păcii trebuie să fie compusă în parlamentul Republicii Democrate a ţării Byteland după regulile impuse de Legea Foarte Importantă. Din păcate, unul dintre obstacole este acela că unii deputaţi nu se înţeleg cu ceilalţi. Comisia trebuie realizată astfel ca următoarele condiţii să fie îndeplinite: fiecare partid trebuie să aibă exact un reprezentant în comisie; dacă doi deputaţi nu se înţeleg, ei nu pot fi ambii membrii ai comisiei. Fiecare partid are exact doi deputaţi în parlament. Toţi număraţi de la $1$ până la $2n (1 &le; n &le; 8000)$. Deputaţii cu numerele $2i-1$ şi $2i$ aparţin celui de al $i$-lea partid. Se vor da $m (0 &le; m &le; 20 000)$ perechi de deputaţi <tex> (a, b) </tex> care nu se înţeleg. Se cere realizarea unei comisii dacă acest lucru este posibil. Un exemplu ar fi pentru trei partide şi perechile <tex> (1, 3) </tex> şi <tex> (2, 4) </tex> care nu se înţeleg comisia alcătuită din membrii <tex> \{1, 4, 5\} </tex>.
 
h3. Soluţie
 
Fiecărui partid îi vom asocia o variabilă; variabila va lua valoarea <tex> 1 </tex> dacă membrul $2i - 1$ al partidului va aparţine comisiei şi valoarea <tex> 0 </tex> dacă membrul $2i$ va aparţine comisiei. Pentru ca din partidul $x$ să existe exact un membru în expresie introducem  <tex> A_{x} \wedge \sim A_{x} </tex>.
Putem exprima că doi membrii ai parlamentului $(2i, 2j)$ nu se înţeleg prin expresia logică <tex> \sim A_{i} \vee \sim A_{j} </tex>. Astfel nu pot ambele variabile <tex> A_{i} </tex> şi <tex> A_{j} </tex> să aibă în acelaşi timp valoarea <tex> 1 </tex> adică $2i$ şi $2j$ nu pot face parte în acelaşi timp din comisie. Dacă cei doi membrii sunt $(2i - 1, 2j - 1)$ atunci îi putem codifica prin expresia <tex> A_{i} \vee A_{j} </tex> astfel <tex> A_{i} </tex> şi <tex> A_{j} </tex> nu pot avea în acelaşi timp valoarea <tex> 0 </tex>, iar dacă membrii sunt $(2i , 2j - 1)$ se poate scrie ca <tex> \sim A_{i} \vee A_{j} </tex> astfel <tex> A_{i} </tex> nu poate avea valoarea <tex> 1 </tex> când <tex> A_{j} </tex> are valoarea <tex> 0 </tex>.
Exemplul din problemă poate fi scris ca expresia logică în modul următor: <tex> A_{1} \wedge \sim A_{1} \wedge A_{2} \wedge \sim A_{2} \wedge A_{3} \wedge \sim A_{3} \wedge (A_{1} \vee A_{2}) \wedge (\sim A_{1} \vee \sim A_{2}) </tex>.
Din nou vom putea folosi cel de {'al patrulea algoritm':2-sat#solutie4} explicat pentru a obţine o rezolvare de complexitate $O(N + M)$.

h2(#orpath). Orpath (Olimpiadă Rusia)

| <tex> 0 </tex> | <tex> 1 </tex> | <tex> 1 </tex> | <tex> 0 </tex> |
| <tex> 0 </tex> | <tex> 0 </tex> | <tex> 0 </tex> | <tex> 0 </tex> |

h2(#probleme). Probleme propuse
 
Pentru a vă familiariza cu subiectul prezentat în acest articol, vă propunem să încercati să rezolvaţi următoarele probleme:
# 'Excursion':www.oi.edu.pl/download/boi-2001.pdf - Baltic Olympiad in Informatics, 2001
# 'Peace Commision':http://www.oi.edu.pl/php/show.php?ac=e100000&module=show&file=zadania/oi8/spokojna - Polish Olympiad in Informatics, 2001
 

h2(#bibliografie). Bibliografie:
# T. H. Cormen, C. E. Leiserson, R. R. Rivest - '_Introducere in Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm