Note de curs, clasele 11-12, 24 octombrie 2013

Recapitulare

Am recapitulat în goană noțiunile introductive despre grafuri:

Pentru a găsi probleme dintr-un capitol anume, nu uitați de http://www.infoarena.ro/cauta-probleme

am scris codul, o mică procedură recursivă. Codul folosește un vector boolean de noduri vizitate
am introdus ideea fictivă de tact, o variabilă globală care crește pe durata parcurgerii
am introdus vectorii d și f, care rețin tactul când un nod este descoperit prima oară, respectiv când este părăsit de rutina DFS
am introdus o a treia stare a unui nod, între alb (nedescoperit) și negru (descoperit): starea gri (în curs de parcurgere)
stiva curentă de apeluri DFS conține noduri gri
am etichetat tipurile de muchii pe durata unei parcurgeri: tree, back, forward, cross
am discutat sumar despre implementarea componentelor conexe pe un graf neorientat folosind parcurgerea DFS

definiție; se aplică grafurilor orientate aciclice (dag)
exemplul cu îmbrăcarea
este o relație de ordine parțială, spre deosebire de relația "<" pe numere, care este o relație de ordine totală
am ilustrat algoritmul cu coada de noduri de grad la intrare 0, de complexitate O(V + E); am scris pseudocodul
sortarea topologică printr-o parcurgere DFS: nodurile sunt afișate în ordine descrescătoare a lui f
- echivalent, la terminarea vizitării unui nod, îl adăugăm la începutul listei-soluție (din nou, vectorul f nu este explicit necesar)
observație: un graf orientat este aciclic ⇔ în DFS nu există back edges

Demonstrație că DFS sortează topologic:

trebuie să arătăm că, pentru orice muchie (u,v), f[v] < f[u]
când muchia (u,v) este explorată, v nu poate fi gri, căci (u,v) ar fi back edge
- dacă v este alb, el devine urmaș al lui u și va fi înnegrit înainte de a reveni la u
- dacă v este negru, f[v] era deja setat, pe când f[u] va fi setat la un moment viitor

definiție; observăm că sunt oarecum similare cu componentele conexe pentru grafuri neorientate
am definit graful transpus, G^T = (V, E^T)
am observat că G^T are aceleași componente tare conexe cu G
am definit graful contractat al lui G, în care fiecare componentă tare conexă este înlocuită cu un singur nod.
am demonstrat (banal) că graful contractat este aciclic
am predat algoritmul cu două parcurgeri BFS, una pe G și una pe G^T în ordinea descrescătoare a valorilor f de la prima parcurgere
am definit d(C) și f(C) (timpii de descoperire / părăsire a unei mulțimi de noduri)
lemă: dacă u ∈ C și v ∈ C' și există muchia (u,v), atunci f(C) > f(C')
- demonstrație: două cazuri, după cum C sau C' a fost descoperită prima
corolar: în G^T, f(C) < f(C') (evident)
demonstrația că algoritmul merge se face prin inducție după numărul de copaci
remarcăm că a doua parcurgere face o sortare topologică a grafului contractat

enunțul problemei
Mihai Andreescu a explicat reducerea 2-SAT la algoritmul de componente tare-conexe