Probleme NP-complete

1. Multimi intern stabile

Definitia 1. Fie G (X, U) un graf orientat. O multime S X este intern stabila (independenta) daca pentru orice x,y I X avem (x,y) U si (y,x) U.

Proprietati. Daca I este familia multimilor intern stabile atunci:

a) II ;

b) SII si A S T AII ;

c) S₁, S₂ I I T S₁S₂ I I .

Definitia 2. O multime S este intern stabila maximala daca pentru orice AII , S A implica S A.

Cu alte cuvinte, S este maximala in raport cu operatia de incluziune.

Definitia 3. Numarul de stabilitate interna al grafului G este valoarea a(G) max .

Multimea intern stabila S pentru care |S| a(G) se numeste multime intern stabila maxima.

Multimi extern stabile

Definitia 4. Fie G (X, U) un graf orientat. O multime T X este extern stabila (dominanta) daca pentru oricey I X T exista xIT astfel incit (x,y) I U.

Proprietati. Daca E este familia multimilor extern stabile atunci:

a) XIE ;

b) TIE si T A X T AIE ;

c) T₁, T₂ I E T T₁T₂ IE ;

Definitia 5. O multime T este extern stabila minimala daca pentru orice AIE , A T implica T A

Cu alte cuvinte, T este minimala in raport cu operatia de incluziune.

Definitia 6. Numarul de stabilitate externa al grafului G este valoarea b(G) min .

Multimea extern stabila T pentru care |T| b(G) se numeste multime extern stabila minima.

Pentru determinarea multimilor extern stabile se defineste mai intii graful bipartit asociat unui graf orientat. Fie G = (X, G) un graf orientat. Definim graful bipartit asociat G' = (X, X', D) astfel:

- X' = este o multime de virfuri;

D:X X' este o aplicatie multivoca definita astfel: y'ID(x) daca si numai daca x y sau yIG(x).

Teorema. T X este extern stabila daca si numai daca D(T) = X' in G'.

Demonstratie. (T) Evident D(T) X', deci ramine sa demonstram ca daca T X este extern stabila atunci X' D(T). Fie y'IX'; daca yIT atunci evident y'ID(y). Daca yIXT atunci exista xIT astfel incit (x,y) I U, deci xIG(y) si atunci y'ID(x) D(T).

) Fie y'IX D(T); cazul y I T este banal; daca y I XT atunci exista xIT astfel incit y'ID(y), de unde rezulta yIG(y) si deci (x,y) I U. n

Nucleul unui graf

Definitie. Fie G = (X, U) un graf orientat. O multime N X este nucleu al grafului G daca este in acelasi timp intern stabila si extern stabila.

Nu orice graf admite un nucleu.

Proprietati. Daca N este nucleu al grafului G, atunci:

a) NG(N) = si NG(N) = X;

b) daca xIX si xIG(x) atunci x N; daca xIX si G(x) = atunci xIN

c) N este intern stabila maximala si extern stabila minimala.

Demonstratie. a) Afirmatia NG(N) = este evidenta deoarece N este multime intern stabila. Intr-adevar, pentru orice x,y I N avem (x,y) U si deci x G(y), de unde rezulta NG(N) = . Pentru a demonstra a doua afirmatie trebuie sa observam ca NG(N) X, deci ramine sa demonstram caX NG(N). Intr-adevar, fie yIX; daca y I NX, atunci (deoarece N este extern stabila), exista xIN astfel incit (x,y) I U. Deci yIG(x) G(N).

c) Presupunem ca N nu este intern stabila maximala, deci exista o multime AII astfel incit N A si N A. Deci exista yIA si y N. Deoarece N este extern stabila, exista xIN astfel incit (x,y) I U, dar xIA si yIA ceea ce contrazice presupunerea ca AII . Deci N este intern stabila maximala. n

Numar cromatic

Definitia 1. Fiind dat un numar natural k, un graf este k-cromatic daca virfurile sale pot fi colorate cu cel mult k culori diferite, astfel incit doua virfuri adiacente sa fie colorate diferit.

Definitia 2. Numarul cromatic al unui graf este cel mai mic numar natural k pentru care graful este k-cromatic si se noteaza cu g(G).

Teorema lui König. Un graf este bicromatic daca si numai daca nu contine cicluri de lungime impara.

Demonstratie. (T) Daca graful este bicromatic, atunci nu poate contine cicluri de lungime impara, deoarece virfurile unui astfel de ciclu nu pot fi colorate cu doua culori fara sa avem doua virfuri adiacente colorate identic.

( ) Consideram un graf fara cicluri impare si conex (daca nu este conex, se considera separat fiecare componenta conexa). Se coloreaza din aproape in aproape virfurile astfel:

- un virf oarecare a se coloreaza in albastru;

- daca un virf x este albastru, se coloreaza in rosu toate virfurile adiacente cu x; daca un virf y este rosu, se coloreaza in albastru toate virfurile adiacente cu y.

Deoarece graful este conex, fiecare virf va fi colorat si nici un virf nu va putea fi colorat in acelasi timp cu doua culori, deoarece el s-ar gasi pe un ciclu de lungime impara. Deci graful este bicromatic. n

Observatii. 1) Teorema lui König se poate formula si astfel: Un graf este bicromatic daca si numai daca este bipartit. Cele doua submultimi disjuncte ale lui X se pot determina dupa colorarea virfurilor, fiecare submultime continind toate virfurile colorate cu aceeasi culoare.

2) Daca un graf bicromatic are cel putin o muchie, atunci numarul sau cromatic este 2.

Definitia 3. Indicele cromatic al unui graf G este numarul minim de culori cu care se pot colora arcele grafului G, astfel incit doua muchii adiacente sa fie colorate cu culori diferite.

Determinarea numarului cromatic. Fie un graf G = (X, U), cu |X| = n. Pentru diferite valori ale lui k (1, 2, 3, ), se incearca sa se formeze aranjamente cu repetitie de k elemente luate cite n (din elementele multimii ) respectindu-se urmatoarea regula: daca (x,y) I U atunci pe pozitiile x si y trebuie sa figureze valori diferite (cele doua virfuri trebuie colorate cu culori diferite). Daca pentru o valoare a lui k au fost epuizate toate aranjamentele cu repetitie, fara sa se poata respecta aceasta conditie, atunci se trece la urmatoarea valoare a lui k. Prima valoare a lui k pentru care se poate determina un aranjament in conditiile date este numarul cromatic al grafului.

Metoda descrisa mai sus este foarte lenta si nu poate fi aplicata decit pentru grafuri de dimensiuni mici. Numarul de operatii necesare pentru determinarea numarului cromatic are un ordin exponential. De aceea in practica ne multumim cu o colorare care nu este optimala, dar care poate fi determinata intr-un timp rezonabil.

Determinarea multimilor intern stabile maxime, a multimilor extern stabile minime si colorarea optima a unui graf sint probleme NP-complete.

Metoda 'Branch and Bound'

Definitie. Un graf orientat G (X,U) este o arborescenta de radacina r daca:

a) G^-1(r)

b) pentru orice x I X (x r) exista un singur drum de la r la x.

Daca orice virf x I X (x r) are proprietatea ca |G(x)|2, avem o arborescenta binara. Virfurilex I X pentru care G(x) = se numesc virfuri terminale.

Pentru rezolvarea unei probleme cu ajutorul metodei 'Branch and Bound' se construieste o arborescenta binara dupa cum urmeaza.

Presupunem ca o problema de programare comporta o multime de solutii S = si ca pe aceasta multime putem defini o functie f : S R al carei minim sa aiba loc pentru solutia optima. Astfel, cautarea solutiei optime se reduce la cautarea minimului functiei f.

Fie b₀ o borna inferioara a valorilor functiei si P_A o proprietate care desface pe S in partitiaS A. Notam cu b₁ b₀ o borna inferioara a valorilor lui f pe A si cu b₁^' b₀ o borna inferioara a valorilor lui f pe

Luam o alta proprietate P_B care desface pe S in partitia S B . Proprietatea P_A P_B este adevarata in AB; analog, P_{A B} este adevarata in A s.a.m.d. (in total patru cazuri).

Nu consideram toate aceste patru cazuri, ci procedam astfel: daca de exemplu b₁^' < b₁, studiem numai B si . Daca mai departe b₂ este borna inferioara a functiei pe B si b₂^' pe , iar b₂ < b₂^', trecem la BC si la B s.a.m.d. In general, continuam intotdeauna sa construim aceasta arborescenta de la acea frunza careia ii corespunde cea mai mica dintre bornele inferioare ale functiei, gasite pina atunci.

Astfel sintem siguri ca valorile succesiv gasite pentru b_i si b_i^' borneaza inferior intreaga multime a solutiilor (intreaga referentiala S), deoarece reuniunea tuturor frunzelor dau evident pe S. De exemplu, in figura avem:

A() B BC) A ) B) A S.

Daca nu se respecta aceasta regula, se poate ajunge la o borna inferioara a functiei pe submultimea aleasa, fara ca ea sa borneze inferior intreaga referentiala. De aceea, de fiecare data se continua pe arborescenta cu acea frunza care are borna asociata de valoare minima. Astfel, pe masura ce cardinalul submultimilor succesive de solutii descreste, borna inferioara a functiei pe intreaga multime creste monoton, deci ea devine egala cu minimul functiei cind, pe aceasta cale, ajungem la o submultime formata dintr-un singur element al lui S, care este solutia optima (prin ipoteza asociata cu minimul functiei). Daca exista mai multe solutii, pot fi gasite toate pe diversele ramuri ale arborescentei care conduc la borne inferioare ale functiei, egale cu minimul acesteia.

Exista unele probleme care se rezolva cu ajutorul acestei metode, fara sa se ceara o solutie optima. In acest caz metoda 'Branch and Bound' se foloseste pentru determinarea tuturor solutiilor problemei.

Dificultati intimpinate in practica:

- gasirea functiei al carei minim sa fie asociat solutiei (solutiilor) optime;

- alegerea proprietatilor separatoare, pentru ca ele sa conduca la bipartitii ale lui S;

- stabilirea unui procedeu adecvat de bornare.

Circuite hamiltoniene minime

Definitie. Un circuit hamiltonian este un circuit care trece prin toate virfurile grafului o singura data.

Sa consideram un graf G=(X,U) orientat si o functie l:U R care asociaza fiecarui arc uIU un numar l(u)ł0. Matricea A asociata grafului se defineste astfel:

Pentru determinarea circuitelor hamiltoniene minime se foloseste algoritmul lui Little, bazat pe metoda 'Branch and Bound'. In acest scop luam drept referentiala multimea C a tuturor circuitelor hamiltoniene din graf si ii asociem functia f : C R₊, unde f(c) este lungimea circuitului c (data de suma valorilor fiecarui arc component). Circuitele pentru care se obtine minimul functiei f sint solutiile optime ale problemei puse.

Proprietatile separatoare (generatoare de bipartitii succesive) vor fi de forma P_ij, prin aceasta intelegind ca luam in considerare circuitele care contin arcul (x_i,x_j). _ij conduce la circuitele care nu contin acest arc. Notam cu C_ij submultimea circuitelor care contin arcul (x_i,x_j) si cu _ij complementara sa.

Pe masura ce inaintam de-a lungul unei ramuri a arborescentei, eliminam arcele folosite, de asemenea si arcele care ar inchide circuite nehamiltoniene (care au un numar de arce mai mic decit |X|).

Pentru bornare definim operatia de reducere a matricei A: scadem din elementele fiecarei linii componenta sa cea mai mica, iar apoi procedam la fel pentru fiecare coloana; fie s suma tuturor elementelor scazute.

Prima borna (b₀) este chiar valoarea s obtinuta in urma operatiei de reducere. Bornele urmatoare se calculeaza tot cu ajutorul unor matrice deduse din A.

Trebuie sa alegem un arc prin care sa efectuam prima bipartitie. Fie acesta (x_i,x_j) ales dintre arcele care au valoarea 0 in matricea redusa.

Calculam o borna inferioara pentru astfel: copiem matricea A in matricea si punem = Ą; dupa ce efectuam reducerea matricei , obtinem borna b₁^' b₀ s. In practica, pentru a ajunge mai repede la minimul functiei f, se analizeaza fiecare arc (x_i,x_j) pentru care a_ij 0, si se alege acel arc pentru care se obtine valoarea s cea mai mare.

Calculam o borna inferioara pentru C_ij astfel: in matricea A suprimam linia i si coloana j (punem peste tot; astfel ordinul matricei A scade cu o unitate) si eliminam toate arcele care ar putea inchide circuite nehamiltoniene; dupa ce efectuam reducerea matricei A, obtinem b₁ b₀ s.

Cu aceasta s-a terminat prima bipartitie si calculul bornelor aferente ei. Fiecarui virf al arborescentei i s-a atasat si matricea de calcul a bornei respective.

In continuare se prezinta urmatoarele posibilitati:

a) b₁ b₁^'. In acest caz se continua pe arborescenta cu multimea C_ij si matricea A.

b) b₁ > b₁^'. In acest caz se continua pe arborescenta cu multimea si matricea

In matricea aleasa pentru continuare (A sau ) se alege un nou arc (x_k,x_l) pentru care a_kl 0, asa cum s-a procedat mai sus. Se ajunge la o noua bipartitie si la calculul bornelor inferioare ale lui f pe C_kl si

Cit timp bornele calculate de-a lungul unei ramuri nu le depasesc pe cele calculate pentru celelalte frunze, ordinul matricelor scade treptat pina ajunge la 1. In acest moment s-a identificat un circuit optim din multimea C.

Algoritmul se poate continua de la celelalte frunze care au borna egala cu minimul functiei f (care este acum cunoscut), pentru a obtine toate solutiile.

Determinarea unui circuit hamiltonian optim intr-un graf este o problema NP-completa.

Anexa A

A.1. Alte tehnici de reprezentare

Reprezentare bazata pe functia G  (liste de succesori)

Se foloseste un vector Ns[] pentru a memora citi succesori are fiecare virf. Se foloseste o matrice Ls[][] pentru a memora lista succesorilor fiecarui virf.

Exemplu (graful orientat din figura 1.2):

Ns: 2 2 1 3 1

primele doua virfuri au cite doi succesori, al treilea unul singur

Ls: 1 3 (virful x₀ are doi succesori: x₁ si x₃)

2 3

4 (virful x₂ are un singur succesor: x₄)

0 2 4

2

Implementare in limbajul C:

unsigned n,j,Ns,*Ls;

Citeste(n); - numar de virfuri

Ns = calloc(n,sizeof(unsigned));

Ls = calloc(n,sizeof(unsigned *));

Ciclu (pentru fiecare virf x I X care are succesori):

Citeste(Ns[x]); - citi succesori are x

Ls[x] = calloc(Ns[x],sizeof(unsigned));

for (j=0; j<Ns[x]; j++)

Citeste(Ls[x][j]) - al j-lea succesor al virfului x

Listele succesorilor fiecarui virf:

for (x=0; x<n; x++)

Eliberare memorie:

free(Ns);

for (j=0; j<n; j++) free(Ls[j]);

free(Ls);

In comparatie cu tehnica descrisa in primul capitol, aceasta solutie consuma ceva mai multa memorie, in schimb nu necesita conversie din lista arcelor. Se recomanda pentru aplicatii de test, in cazul in care graful este descris cu ajutorul functiei G  astfel:

- n, numarul de virfuri;

- pentru fiecare virf x:

- numarul de succesori;

- pentru fiecare succesor: indexul acestuia si costul legaturii.

Matricea de adiacenta

Pentru grafuri neponderate se foloseste o matrice A_{n n}

a_ij =

Graful orientat din figura 1.2 se reprezinta astfel:

Un graf ponderat poate fi reprezentat astfel:

a_ij =

Este contraindicata pentru aplicatii practice deoarece necesita un volum de memorie de ordin O(n²), si un timp de prelucrare de ordin cel putin O(n²). Am amintit aici si aceasta metoda deoarece este prezenta in aproape toate manualele pentru elevii de la profilul matematica-informatica.

Listele succesorilor fiecarui virf (limbajul C):

for (i=0; i<n; i++)

A.2. Algoritmi bazati pe matricea de adiacenta

Matricea drumurilor

Fie A^k puterea k a matricei de adiacenta (k > 0). Un element are urmatoarea semnificatie: numarul de drumuri distincte de la virful x_i la virful x_j care au lungimea (numar de arce) k.

Pentru a decide daca exista drumuri de la virful x_i la virful x_j se determina toate puterile k ( 1, 2, , n) ale matricei k, operatie care necesita un timp de ordin O(n⁴). Daca avem nevoie doar sa stim intre care virfuri exista drumuri, putem folosi o solutie mai simpla bazata pe algoritmul Roy-Warshall:

Algoritm Roy-Warshall;

Intrare. A_{n n}, matricea de adiacenta a unui graf orientat.

Iesire. D_{n n}, matricea drumurilor grafului dat.

begin

D A;

for (each k I X) do

for (each i I X) do

for (each j I X) do

d_ij d_ij d_ik d_kj;

end (algoritm).

si sint operatiile logice OR si AND, considerind ca matricea D are coeficienti valori booleene. Se observa ca acest algoritm are complexitate de ordin O(n³).

Valoarea d_ij indica daca intre virfurile x_i si x_j exista cel putin un drum (d_ij 1) sau nici unul (d_ij 0).

Componente tare conexe

Doua virfuri x_i si x_j se afla in aceeasi componenta conexa daca si numai daca d_ij d_ji 1. Rezulta

Algoritm Comp-tare-conexe;

Intrare. Matricea D a drumurilor unui graf.

Iesire. Un masiv C: componentele tare conexe ale acestuia.

begin

nc 0;

for (each i I X) do C[i] 0;

for (each i I X) do

if (C[i] 0) then begin

nc nc 1;

for (each j I X) do

if (c_ij c_ji 1) then

C[j] nc;

end

end (algoritm).

Acest algoritm are complexitate de ordin O(n²), si deoarece se bazeaza pe algoritmul Roy-Warshall, rezulta ca determinarea componentelor tare conexe pe baza matricei drumurilor necesita un timp de ordin O(n³).

Drumuri de cost minim

Algoritmul lui Floyd este foarte asemanator cu algoritmul Roy-Warshall prezentat mai sus. Spre deosebire de algoritmii prezentati in capitolul patru, unde pentru reconstituirea drumului minim am folosit un masiv, acest algoritm foloseste o matrice.

Algoritm Drum-Cost-Minim;

Intrare. A_{n n}, matricea de adiacenta a unui graf orientat ponderat.

Iesire. C_{n n}: matricea de adiacenta a unui graf orientat ponderat.

P_{n n}: matricea de precedenta pentru reconstituirea unui drum.

begin

C A;

for (each i I X) do

for (each j I X) do

p_ij i;

for (each k I X) do

for (each i I X) do

for (each j I X) do begin

w c_ik c_kj;

if (c_ij > w) then begin

c_ij w; p_ij p_kj;

end

end

end (algoritm).

Explicatie. Daca c_ij > c_ik c_kj atunci exista un alt drum de la x_i la x_j, mai bun decit cel depistat pina in prezent, si care trece prin x_k. p_ij reprezinta virful predecesor virfului x_j intr-un drum de la x_i la x_j. Daca un drum mai bun de la x_i la x_j trece prin x_k, atunci virful p_kj este predecesor intr-un astfel de drum (figura A.1).

Acest algoritm are complexitate de ordin O(n³), si necesita memorie de ordin O(n²). Un drum de la s la t se reconstituie astfel:

Write(t); x t;

while (x s) do begin

x p_sx; Write(x);

end

Figura A.1. Modificarea relatiei de precedenta.