Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice



Acasa » referate » matematica
Probleme NP-complete

Probleme NP-complete



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) S1, S2 I I T S1S2 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) T1, T2 I E T T1T2 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 b0 o borna inferioara a valorilor functiei si PA o proprietate care desface pe S in partitiaS A. Notam cu b1 b0 o borna inferioara a valorilor lui f pe A si cu b1' b0 o borna inferioara a valorilor lui f pe

Luam o alta proprietate PB care desface pe S in partitia S B . Proprietatea PA PB este adevarata in AB; analog, PA 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 b1' < b1, studiem numai B si . Daca mai departe b2 este borna inferioara a functiei pe B si b2' pe , iar b2 < b2', 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 bi si bi' 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 Pij, prin aceasta intelegind ca luam in considerare circuitele care contin arcul (xi,xj). ij conduce la circuitele care nu contin acest arc. Notam cu Cij submultimea circuitelor care contin arcul (xi,xj) 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 (b0) 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 (xi,xj) 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 b1' b0 s. In practica, pentru a ajunge mai repede la minimul functiei f, se analizeaza fiecare arc (xi,xj) pentru care aij 0, si se alege acel arc pentru care se obtine valoarea s cea mai mare.

Calculam o borna inferioara pentru Cij 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 b1 b0 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) b1 b1'. In acest caz se continua pe arborescenta cu multimea Cij si matricea A.

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

In matricea aleasa pentru continuare (A sau ) se alege un nou arc (xk,xl) pentru care akl 0, asa cum s-a procedat mai sus. Se ajunge la o noua bipartitie si la calculul bornelor inferioare ale lui f pe Ckl 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 x0 are doi succesori: x1 si x3)

2 3

4 (virful x2 are un singur succesor: x4)

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 An n

aij =

Graful orientat din figura 1.2 se reprezinta astfel:


Un graf ponderat poate fi reprezentat astfel:

aij =


Este contraindicata pentru aplicatii practice deoarece necesita un volum de memorie de ordin O(n2), si un timp de prelucrare de ordin cel putin O(n2). 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 Ak puterea k a matricei de adiacenta (k> 0). Un element are urmatoarea semnificatie: numarul de drumuri distincte de la virful xi la virful xj care au lungimea (numar de arce) k.

Pentru a decide daca exista drumuri de la virful xi la virful xj se determina toate puterile k ( 1, 2, , n) ale matricei k, operatie care necesita un timp de ordin O(n4). 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. An n, matricea de adiacenta a unui graf orientat.

Iesire. Dn 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

dij dij dik dkj;

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(n3).

Valoarea dij indica daca intre virfurile xi si xj exista cel putin un drum (dij 1) sau nici unul (dij 0).


Componente tare conexe


Doua virfuri xi si xj se afla in aceeasi componenta conexa daca si numai daca dij dji 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 (cij cji 1) then

C[j] nc;

end

end (algoritm).


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


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. An n, matricea de adiacenta a unui graf orientat ponderat.

Iesire. Cn n: matricea de adiacenta a unui graf orientat ponderat.

Pn n: matricea de precedenta pentru reconstituirea unui drum.

begin

C A;

for (each i I X) do

for (each j I X) do

pij i;

for (each k I X) do

for (each i I X) do

for (each j I X) do begin

w cik ckj;

if (cij > w) then begin

cij w; pij pkj;

end

end

end (algoritm).


Explicatie. Daca cij > cik ckj atunci exista un alt drum de la xi la xj, mai bun decit cel depistat pina in prezent, si care trece prin xk. pij reprezinta virful predecesor virfului xj intr-un drum de la xi la xj. Daca un drum mai bun de la xi la xj trece prin xk, atunci virful pkj este predecesor intr-un astfel de drum (figura A.1).


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


Write(t); x t;

while (x s) do begin

x psx; Write(x);

end



Figura A.1. Modificarea relatiei de precedenta.






Politica de confidentialitate

.com Copyright © 2020 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 SCHITA DE PROIECT DIDACTIC GEOGRAFIE CLASA: a IX-a - Unitatile majore ale reliefului terestru
 PROIECT DIDACTIC 5-7 ani Educatia limbajului - Cate cuvinte am spus?
 Proiect atestat Tehnician Electronist - AMPLIFICATOARE ELECTRONICE
 Proiect - masurarea si controlul marimilor geometrice

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 LUCRARE DE DIPLOMA MANAGEMENT - MANAGEMENTUL CALITATII APLICAT IN DOMENIUL FABRICARII BERII. STUDIU DE CAZ - FABRICA DE BERE SEBES
 Lucrare de diploma tehnologia confectiilor din piele si inlocuitor - proiectarea constructiv tehnologica a unui produs de incaltaminte tip cizma scurt

Lucrari licenta

vezi toate lucrarile de licenta
 LUCRARE DE LICENTA CONTABILITATE - ANALIZA EFICIENTEI ECONOMICE – CAI DE CRESTERE LA S.C. CONSTRUCTIA S.A TG-JIU
 Lucrare de licenta sport - Jocul de volei
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 PROIECT ATESTAT MATEMATICA-INFORMATICA - CALUTUL INTELIGENT
 Proiect atestat Tehnician Electronist - AMPLIFICATOARE ELECTRONICE
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 ATESTAT PROFESIONAL TURISM SI ALIMENTATIE PUBLICA, TEHNICIAN IN TURISM




Test de evaluare la algebra
Tetraedre echifaciale
Rezolvarea iterative a sistemelor de ecuatii lineare- Metoda Gauss-Siedel
Integrale rationale si reductibile la integrale rationale
Determinantul
Modele cu ecuatii simultane
Coeficientul de corelatie pentru 2 variabile aleatoare
PREMISELE FORMALIZARII RISCULUI




Termeni si conditii
Contact
Creeaza si tu