h2. Indicaţii de rezolvare

Articolul 'Problema 2-satisfiabilităţii':2-sat prezintă fiecare dintre soluţiile de mai jos în detaliu. Iată o schiţă...

Articolul 'Problema 2-satisfiabilităţii':http://infoarena.ro/2-sat prezintă fiecare dintre soluţiile de mai jos în detaliu. Iată o schiţă...

O soluţie evidentă este încercarea celor $2^N^$ configuraţii posibile pentru termenii expresiei şi verificarea lor. Această abordare duce însă la o complexitate cu ordinul de excuţie $O(2^N^ * M)$. Cu această soluţie se obţin '$20$ de puncte':job_detail/382683?action=view-source.

În articolul de mai sus se arată cum se ajunge la soluţie. Iată pe scurt cum se procedează. În primul rând, graful va fi împărţit în 'componente tare-conexe':problema/ctc. O proprietate importantă a componentelor conexe este că în fiecare componentă există un ciclu ce conţine toate vârfurile sale. Astfel, toate nodurile dintr-o componentă tare conexă vor avea, în mod necesar, aceeaşi valoare de adevăr. Dacă nu ar fi astfel, ar exista pe ciclu o valoare „true” ce ar implica o valoare „false”. Observăm că dacă un nod şi negaţia sa se găsesc în aceeaşi componentă tare conexă atunci nu există soluţie. Din câteva proprietăţi de simetrie, pe care le puteţi găsi în articol, se deduce că pentru o componentă <tex> c </tex> în care se găseşte o implicaţie <tex> x_{i} \rightarrow x_{j} </tex>, va exista o componentă <tex> \bar{c} </tex> ce va conţine implicaţia echivalentă <tex> \bar{x_{j}} \rightarrow \bar{x_{i}} </tex>. În continuare, vom contracta componentele tare-conexe într-un nod, rezultând un graf orientat aciclic. Prin gradul unei componente tare-conexe vom înţelege gradul nodului asociat din acest graf orientat aciclic. Utilizând o 'sortare topologică':problema/sortaret vom împerechea succesiv componentele după cum urmează. Se va alege o componentă cu gradul de intrare zero. Din componenta sa pereche, datorită simetriei de care aminteam, nu va ieşi nicio muchie. Astfel, toate nodurile din componenta tare-conexă cu gradul de intrare zero vor avea valoarea de adevăr „false”, pentru a nu impune restricţii asupra celorlalte noduri, iar toate nodurile din componenta pereche vor primi valoarea de adevăr „true”, întrucât din aceasta nu mai iese nicio muchie şi astfel nu va influenţa alte valori. Ulterior, se vor elimina cele două noduri şi se va relua procedeul.

A se preciza ca in general sortarea topologica nu mai trebuie implementata. Algoritmul lui Tarjan adauga componentele in ordinea inversa a sortarii topologice, iar algoritmul lui Kosaraju fie exact sortarea topologica, fie invera ei (depinde daca se inverseaza sau nu ordinea celor doua parcurgeri). Prin inversa a se intelege ca prima componenta e ultima,a doua penultima s.a.m.d.
 

Soluţia de '100 de puncte':job_detail/382602?action=view-source are complexitatea $O(M + N)$.
h2. Aplicaţii