Colorarea grafurilor:n teoria grafurilor,colorarea grafurilorconstn atribuirea de culori vrfurilor unui graf astfel ca oricare douvrfuri adiacente snu aibaceeai culoare. n mod analog,colorarea muchiilorconstn atribuirea unei culori fiecrei muchii n parte, astfel nct oricare doumuchii incidente snu aibaceeai culoare, iarcolorarea feelorunui graf planar atribuie o culoare fiecrei fee in parte,inndu-secont de faptul coricare douastfel de fee, ce au o frontier comun, nu pot avea aceeai culoare.O3-colorareeste suficientacestui graf, ns, dacs-arfolosi mai puine culori ar rezulta noduri (vrfuri) adiacente de aceeai culoare.Gsirea numrului minim de culori necesare colorrii unui graf oarecare are dificultate NP.Cel mai mic numr de culori necesare colorrii unui graf se numetenumrul cromaticcorespunztor. De exemplu, numrul cromatic al unui graf completKncunvrfuri (un graf cu o muchie ntre oricare douvrfuri), este(Kn)=n.Un graf cruia i poate fi atribuitok-colorare(corespunztoare) estek-colorabil,i estek-cromaticdacnumrul su cromatic este chiark.Problema gsirii unei colorri minime a unui graf are o dificultate- NP. Problema deciziei corespunztoare (existo colorare care folosete cel multkculori?) are o complexitate de ordinul NP, reprezentnd, la origine, una din cele 21 de probleme ale lui KarpNP-complete.RmneNP-completchiari n cazul grafurilor planare de grad cel mult 4, aa cum a fost demonstrat de ctre Gareyi Johnson n 1974, chiar dacn cazul grafurilor planare este trivial(n. demonstraia) pentruk>3 (acest lucrudatorndu-seteoremei celor patru culori). Exist, totui, unii algoritmi de aproximare eficieni, care folosesc programarea semidefinit.Proprieti ale(G):1.(G) = 1 dac i numai dacG este total neconex. 2.(G)3 dac i numai dacGare unciclu impar(echivalent, dacGnu este bipartit).3.(G) (G).4.(G)(G)+1. 5.(G)(G) pentru G conex, doar dacnu cumva G este ungraf completsau un ciclu impar (Teorema lui Brook).6.(G)4, pentru orice graf planar G. Acest faimos rezultat este numitTeorema celor patruculori.Aici,(G)reprezintgradul maxim, iar(G), numrul clic.Polinomul cromaticcontorizeaznumrul posibilitilor de colorare a unui graf , utiliznd un numr prestabilit de culori.Polinomul cromaticeste o funcieP(G,t)ce contorizeaznumrult-colorrilorluiG. Aa cum indic i numele, pentru un grafGdat funcia estentr-adevrpolinomialnt.Polinomul cromaticconine cel puin la fel de multe informaii legate de colorabilitatea lui G cainumrul cromatic.Colorarea Hartilor: Fiind data o harta cu n tari, se cer toate solutiile de colorare a hartii, utilizand m culori, m>=4, astfel incat doua tari vecine sa nu aiba aceeasi culoare.Algoritm:P1).Se introduc datele de intrare(n,m si matricea vecinilor). P2).Se initializeaza nivelul k al stivei.P3).Cat timp exista nivele in stiva executam pasii urmatori.P4).Cautam un succesor pe nivelul k al stivei pana cand gasim unul care nu depaseste nr max de culori, apoi verificam daca este valid (indeplineste conditiile ca elem gasit in stiva sa fie diferit de celelalte elemente si in plus tara i sa nu fie vecina cu tara k)P5).Daca s-a gasit un astfel de elem si daca e o solutie a problemei se tipareste, iar in caz contrar se trece la nivelul urmator al stivei si se initializeaza stiva.P6).In cazul in care nu s-a gasit nici o solutie pe nivelul k, coboram la niv anterior sa cautam si alte solutii valide.Harta este furnizata programului cu ajutorul unei matrice Anxn, A(i,j)=1, daca tara i se invecineaza cu tara j si valoarea 0 in caz contrar.Matricea A este simetrica. Pentru rezolvarea problemei se utilizeaza stiva st, unde nivelul k al stivei simbolizeaza tara k, iar st[k] culoarea atasata tarii k.Stiva are inaltimea n (nr de tari) si pe fiecare nivel la valori intre 1 si m.