1. Teoria grafurilor a) Concepte de baza in teoria grafurilor b) Notiunea de graf c) Grafuri neorientate d) Notiunea de lant si ciclu e) Parcurgerea grafurilor Parcurgerea in latime Parcurgerea in adancime 2. Grafuri hamiltoniene si euleriene 3. Curiozitati a) Grafuri euleriene b) Grafuri hamiltoniene

1.TEORIA GRAFURILORConform DEX notiunea de graf reprezinta ansamblul a doua multimi disjuncte, intre care s-a stabilit o corespondenta. Teoria grafurilor este disciplina care studiaza proprietatile topologice ale structurii grafelor. Originile teoriei grafurilor se gasesc in rezolvarea unor probleme de jocuri 555c21f 51;i amuzamente matematice care au atras atentia matematicienilor (Euler , Hamilton). Aceasta problema celebra a fost enuntata de matematicianul Euler, care impreuna cu Hamilton au fost cei care au pus bazele teoriei grafurilor. Data nasterii teoriei grafurilor este considerata a fi anul 1736, cand matematicianul Leonhard Euler a publicat un articol in care a clarificat 'Problema celor 7 poduri din Kaliningrad' (Euler s-a intrebat daca poate face o plimbare care sa includa in traseul sau toate cele 7 poduri, astfel incat fiecare pod sa fie traversat o singura data si sa revina la punctul de plecare).

In general, pentru situatiile care necesita la rezolvare un oarecare efort mintal (si un caz tipic este cel al celor din economie), se cauta, in primul rand, o metoda de reprezentare a lor care sa permita receptarea intregii probleme dintr-o privire (pe cat posibil) si prin care sa se evidentieze cat mai clar toate aspectele acesteia. In acest scop se folosesc imagini grafice gen diagrame, schite, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate in special pentru vizualizarea sistemelor si situatiilor complexe. In general, vom reprezenta componentele acestora prin puncte in plan iar relatiile (legaturile, dependentele, influentele etc) dintre componente prin arce de curba cu extremitatile

in punctele corespunzatoare. Intre doua puncte pot exista unul sau mai multe segmente (in functie de cate relatii dintre acestea, care ne intereseaza, exista) iar segmentelor li se pot asocia sau nu orientari (dupa cum se influenteaza cele doua componente intre ele), numere care sa exprime intensitatea relatiilor dintre componente etc. Este evident, totusi, ca aceasta metoda are limite, atat din punct de vedere uman (prea multe puncte si segmente vor face desenul atat de complicat incat se va pierde chiar scopul pentru care a fost creat claritatea si simplitatea reprezentarii, aceasta devenind neinteligibila) cat si din punct de vedere al tehnicii de calcul (un calculator nu poate 'privi' un desen ca un om). Din acest motiv, alaturi de expunerea naiv-intuitiva a ceea ce este un graf, data mai sus, se impune atat o definitie riguroasa cat si alte modalitati de reprezentare a acestora, adecvate in general rezolvarilor matematice. Se numeste multigraf un triplet G = (X, A, f) in care X si A sunt doua multimi iar f este o functie, definita pe produsul vectorial al lui X cu el insusi (X2 = XX), care ia valori in multimea partilor multimii A (notata P(A)). Multimea X se numeste multimea nodurilor multigrafului si elementele sale se numesc noduri (sau varfuri) ale multigrafului, iar A reprezinta multimea relatiilor (legaturilor) posibile intre doua noduri ale multigrafului. Se numeste graf orientat un multigraf in care multimea A are un singur element: A . In acest caz multimea partilor multimii A are doar doua elemente: multimea vida si intreaga multime A. Daca unei perechi orientate (xi, xj) din X2 i se asociaza prin functia f multimea A atunci spunem ca exista arc de la nodul xi la nodul xj iar perechea (xi,xj) se va numi arcul (xi,xj). Nodul xi se numeste nod initial sau extremitate initiala a arcului (xi,xj) iar nodul xj se numeste nod final sau extremitate finala a arcului (xi,xj). Arcul (xi,xj) este incident spre interior varfului xj si incident spre exterior varfului xi. Daca pentru un arc nodul initial coincide cu nodul final atunci acesta se numeste bucla. Nodurile xi si xj se vor numi adiacente daca exista cel putin unul din arcele (xi,xj) si (xj,xi). Daca unei perechi orientate (xi, xj) din X2 i se asociaza prin functia f multimea vida atunci spunem ca nu exista arc de la nodul xi la nodul xj. Este evident ca a cunoaste un graf orientat este echivalent cu a cunoaste varfurile si arcele sale. Din acest motiv putem defini un graf orientat prin perechea (X,U), unde X este multimea varfurilor sale iar U multimea arcelor sale. De asemenea, putem cunoaste un graf orientat cunoscand multimea nodurilor si, pentru fiecare nod, multimea arcelor incidente spre exterior. Din acest motiv putem defini un graf orientat ca o pereche (X,) unde X este perechea nodurilor iar este o functie definita pe X cu valori multimea partilor lui X, valoarea acesteia intr-un nod xi, (xi) X fiind multimea nodurilor adiacente nodului xi, prin arce pentru care xi este extremitatea initiala. Se numeste graf neorientat un multigraf in care multimea A are un singur element iar functia f are proprietatea: f[(xi,xj)] = f[(xj,xi)] , oricare ar fi nodurile xi si xj din X

In aceste conditii, daca f[(xi,xj)] = f[(xj,xi)] = A atunci perechea neorientata este o muchie iar daca f[(xi,xj)] = f[(xj,xi)] = spunem ca nu exista muchie intre varfurile xi si xj. Deoarece, in cele mai multe din cazurile practice care vor fi analizate in acest capitol, situatia este modelata matematic printr-un graf orientat, vom folosi, pentru simplificarea expunerii, denumirea de graf in locul celei de graf orientat iar in cazul in care graful este neorientat vom specifica acest fapt la momentul respectiv.

Concepte de baza in teoria grafurilor1. semigraf interior al unui nod xk: este multimea arcelor = care sunt incidente spre interior nodului xk; 2. semigraf exterior al unui nod xk: este multimea arcelor = care sunt incidente spre exterior nodului xk; 3. semigradul interior al unui nod xk: este numarul arcelor care sunt incidente spre interior nodului xk = cardinalul lui si se noteaza cu ; kxUkx 4. semigradul exterior al unui nod xk: este numarul arcelor care sunt incidente spre exterior nodului xk = cardinalul lui si se noteaza cu ; +kxU+kx 5. gradul unui nod xk: este suma semigradelor nodului xk: = + ; kx+kxkx 6. nod izolat: este un nod cu gradul 0; 7 . nod suspendat: este un nod cu gradul 1; 8. arce adiacente: arce care au o extremitate comuna; 9 . drum intr-un graf: o multime ordonata de noduri ale grafului: (x1, x2, , xk), cu proprietatea ca exista in graf toate arcele de forma (xi,xi+1) i = 1,,k-1; 10. lungimea unui drum: este numarul arcelor care il formeaza; 11. drum elementar: un drum in care fiecare nod apare o singura data; 12. drum simplu: un drum in care fiecare arc apare o singura data; 13. putere de atingere a unui nod xi < X in graful G: numarul de noduri la care se poate ajunge din xi. Puterea de atingere se noteaza cu p(xi), 1 i n si evident p(xi) . +ix 14. drum hamiltonian: un drum elementar care trece prin toate nodurile grafului; 15. drum eulerian: un drum simplu care contine toate arcele grafului; 16. lant: un drum in care arcele nu au neaparat acelasi sens de parcurgere; 17. circuit: un drum in care nodul initial coincide cu cel final; 18. circuit elementar: un drum in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial; 19. circuit simplu: un drum in care fiecare arc apare o singura data; 20. circuit hamiltonian: un circuit care trece prin toate nodurile grafului; 21. ciclu: este un circuit in care arcele nu au neaparat acelasi sens de parcurgere;

22. ciclu elementar: un ciclu in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial; 23. ciclu simplu: un ciclu in care fiecare arc apare o singura data; Observatie: Intrun graf neorientat notiunile de drum si lant sunt echivalente si de asemenea cele de circuit si ciclu. 24. graf partial al unui graf G = (X,U): este un graf G'(X,U') cu U' U; 25. subgraf al unui graf G = (X,): este un graf G'(X',') unde X' X si '(xi) = (xi) X' pentru orice xi X'; 113 Elemente de teoria grafurilor 26. graf redus al unui graf G = (X,U): este un graf G*(X*,U*) unde X* este formata din multimile unei partitii de multimi nevide ale lui X, iar () exista doar daca i j si exista cel putin un arc in U, de la un nod din la un nod din *iX,*jX*iX*jX. 27. graf tare conex: este un graf in care intre oricare doua noduri exista cel putin un drum; 28. graf simplu conex: este un graf in care intre oricare doua noduri exista cel putin un lant; Observatie: Pentru grafuri neorientat notiunile de tare conex si simplu conex sunt echivalente, graful numindu-se doar conex; 29. componenta tare conexa a unui graf G = (X,U): este un subgraf al lui G care este tare conex si nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, intre oricare doua noduri din componenta exista cel putin un drum si nu mai exista nici un nod in afara componentei legat printr-un drum de un nod al componentei).

Notiunea de grafDesi definitiile date anterior ,referitoare la notiunea de graf sunt clare si complete, tin sa dezvolt aceasta pentru o mai buna intelegere. Se numeste graf orice multime finita X prevazuta cu o relatie binara interna U. Graful se noteaza G=(X,U). Grafurile pot fi de doua tipuri: Grafuri orientate (digrafuri); Grafuri neorientate. Se numeste graf orientat perechea ordonata G= (X,U) in care relatia binara nu este simetrica. Se numeste graf neorientat perechea ordonata G=(X,U) in care relatia binara este simetrica.

Grafuri neorientateDefinitie :Se numeste graf neorientat o pereche ordonata de multimi (X,U), unde : X este o multime finita si nevida de elemente numite varfuri sau noduri U este o multime de perechi neordonate de cate doua elemente din X, numite muchii sau arce. Asadar, un graf neorientat poate fi reprezentat sub forma unei figuri geometrice alcatuita din puncte (varfuri, noduri) si linii drepte sau curbe care unesc aceste puncte (muchii, arce). Vom folosi: pentru grafuri neorientate termenii de varf si muchie ; pentru grafuri orientate termenii de nod si arc Daca o muchie trece prin nodurile x si y, atunci ea se noteaza (x,y) sau [x,y]. Pe caz general, intr-un graf neorientat G = (X,U) notam : m numarul muchiilor ; n numarul nodurilor ; X = multimea varfurilor ; U = multimea muchiilor ; o muchie uk este o pereche neordonata (a,b) alcatuita din doua elemente din X.

Definitie: Pentru o muchie uk = (a,b) , vom spune ca : varfurile a si b sunt adiacente si se numesc extremitatile muchiei uk ; muchia uk si varful a sunt incidente in graf. La fel, muchia uk si varful b ; muchia (a,b) este totuna cu (b,a) (nu exista o orientare a muchiei). Definitie: Gradul unui varf x, notat d(x), reprezinta numarul muchiilor care trec prin nodul x (incidente cu nodul x). Un varf care are gradul 0 se numeste varf izolat. Un varf care are gradul 1 se numste varf terminal.

Teorema: Intr-un graf G = (X,U), cu n varfuri si m muchii , suma gradelor tuturor varfurilor este egala cu 2 * numarul muchiilor. Exemplu Avem pentru graful considerat : -X= multimea varfurilor (nodurilor) - U= multimea muchiilor (arcelor) - Muchiile sunt : u1 = (1,2) ; u2 = (2,3) ; u3 = (3,4) ; u4 = (2,4) ; u5 = (5,6) ; - d(1) = 1 ; d(2) = 3 ; d(3) = 2 ; d(4) = 2 ; d(5) = 1 ; d(6) = 1 ; d(7) = 0 ; - varful 7 este varf izolat ; vafurile 5 si 6 sunt varfuri terminale .

Metode de reprezentare Este o matrice A cu n linii si n coloane, in care elementele a[i,j] se definesc astfel: Deoarece muchia (a,b) este totuna cu muchia (b,a), rezulta ca a[i,j] = a[j,i] , oricare ar fi i ,j {1,2,,n} Din acest motiv, matricea de adiacenta pentru un graf neorientat este simetrica fata de diagonala principala.

Pentru fiecare nod i , cu i {1,2,,n}, formam lista vecinilor lui i. Aceasta cuprinde toate nodurile care sunt extremitati ale muchiilor ce trec prin nodul i.

Citirea unui graf memorat cu ajutorul matricei de adiacenta Varianta 1: Citirea numarului de varfuri,citirea regiunii de deasupra diagonalei principale urmata de simetrizare. var a:array[1..120,1..120] of 0..1; x,d,i,j,n:byte; begin write(nr de varfuri:=);readln(n); for i:=1 to n-1 do for j:=i+1 to n do begin write(a[,i,,,j,]:=);readln(a[i,j]); a[j,i]:=a[i,j]; end; end. Varianta 2: Se citesc n-nr de varfuri,m-nr de muchii; -initializarea matricei de adiacenta cu zero; -citirea extremitatii fiecarei muchii; -completarea matricei de adiacenta. var a:array[1..120,1..120] of 0..1; x,d,i,j,n:byte; begin write(n:=);readln(n); write(m:=);readln(m); for i:=1 to n do for j:=1 to n do a[i,j]:=0; for i:=1 to m do begin writeln(Muchia ,i, este:); readln(x,y); a[x,y]:=1; a[y,x]:=1; end; end.

Definitie: Fie graful G = (X,U). Un graf partial al lui G este un graf G1 = (X,V), cu V U. Altfel spus, un graf partial G1 al lui G, este chiar G, sau se obtine din G pastrand toate varfurile si suprimand niste muchii.

Definitie. Fie graful G = (X,U). Un subgraf al lui G este un graf G1 = (Y,T), cu Y X si T U, iar T va contine numai muchiile care au ambele extremitati in Y. Altfel spus, un subgraf G1 al lui G se obtine din G eliminand niste varfuri si pastrand doar acele muchii care au ambele extremitati in multimea varfurilor ramase.

Exemplu :

a)Eliminam muchiile care trec prin nodul 4 graf partial

Am eliminat muchiile u3 si u4, pastrand toate varfurile. b)Eliminam varfurile 5,6,7 si muchiile corespunzatoare(u5) subgraf

Notiunile de lant si cicluDefinitie:Se numeste lant in graful G, o succesiune de varfuri L = (z1,z2,,zk), unde z1,z2,,zk X, cu proprietatea ca oricare doua varfuri consecutive sunt adiacente, adica exista muchiile [z1,z2], [z2,z3],, [zk-1,zk] U. Varfurile z1 si zk se numesc extremitatile lantului, iar numarul de muchii care intra in componenta sa reprezinta lungimea lantului. Daca varfurile z1,z2,,zk sunt distincte doua cate doua, lantul se numeste elementar. In caz contrar, lantul este ne-elementar.

Exemplu :

L1 = (1,2,3,4) - lant elementar L2 = (1,2,4,3,2,3,4) - lant ne-elementar L3 = (2,4,3,2,1) lant ne-elementar L4 = (6,5,1,2,3,4) -lant elementar

Definitie: Se numeste ciclu intr-un graf, un lant L = (z1,z2,,zk) cu proprietatea ca z1 = zk si muchiile [z1,z2], [z2,z3],, [zk-1,zk] sunt distincte doua cate doua. Def. Daca intr-un ciclu, toate varfurile cu exceptia primului si a ultimului sunt distincte doua cate doua, atunci ciclu se numeste elementar. In caz contrar, el este ne-elementar. C1 = (2,3,4,2) - ciclu elementar C2 = (1,2,4,3,1) - ciclu elementar C3 = (5,2,4,3,1,5 - ciclu elementar

C4 = (1,2,3,4,2,5,1) - ciclu ne-elementar C5 = (5,2,3,4,2,1,5) - ciclu ne-elementar Obs. In cadrul unui lant, muchiile se pot repeta, dar in cadrul unui ciclu ele trebuie sa fie distincte. Definitie:Un graf G este conex daca oricare ar fi doua varfuri ale sale, exista un lant care le leaga. Obs. Intr-un graf conex, luand oricare doua varfuri , putem gasi cel putin un traseu(lant) care porneste dintr-un varf si ajunge in celalalt. Definitie:Se numeste componenta conexa a grafului G =(X,U), un subgraf G1=(X1,U1) a lui G,conex, cu proprietatea ca nu exista nici un lant care sa lege un varf din X1 cu un varf din X-X1. Exemplu:

In acest exemplu exista 3 componente conexe: G1 =(X1,U1), cu X1= si U1= G2 =(X2,U2), cu X2= si U2= G3 =(X3,U3), cu X3= si U1=

Parcurgerea grafurilorParcurgerea grafurilor se realizeaza cu scopul vizitarii varfurilor acestora.Fiecare varf se va vizita o singura data,cu scopul prelucrarii informatiei. Parcurgerea:-in latime -in adancime Parcurgerea in latime (BF-Breath First) Se viziteaza la inceput varful initial,apoi se viziteaza vecinii nevizitati ai acestuia,apoi vecinii nevizitati ai vecinilor si asa mai departe. Program pentru BF Se va utiliza o coada.Initial,in coada se afla doar varful initial,la fiecare pas se va prelucra varful aflat la inceputul cozii.Consideram toti vecinii nevizitati ai acestuia si ii adaugam in coada dupa care, varful fiind prelucrat va fi eliminat din coada.Prelucrarea se va face atat timp cat exista elemente in coada. Pentru a retine varfurile vizitate folosim un vector boolean cu semnificatia:

viz[i]=true,daca varful i a fost vizitat =false,altfel Initial,toate varfurile sunt nevizitate. var c:array[1..20]f byte; a:array[1..20,1..20]of 0..1; viz:array[1..20]of boolean; vi,vc,n,u,i,p:byte; begin write(varf initial:=);readln(vi); for i:=1 to n do viz[i]:=false; p:=1; u:=1; c[1]:=vi; viz[vi]:=true; while p graf hamiltonian (muchiile sunt distincte doua cate doua)

Exemplul2:

Graful din acest exemplu este hamiltonian, deoarece ciclu C =[2,5,1,3,4,2] este elementar (pleaca din varful 2 si se intoarce tot in 2, iar muchiile [2,5], [5,1], [1,3], [3,4], [4,2] sunt distincte doua cate doua) si in plus contine toate varfurile. Definitie: Se numeste lant hamiltonian intr-un graf, un lant elementar care contine toate varfurile grafului. Teorema: Daca intr-un graf G(X,U) cu n3 varfuri, gradul fiecarui varf x verifica conditia , atunci graful este hamiltonian.

Definitie: Se numeste ciclu eulerian intr-un graf, un ciclu care contine toate muchiile grafului. Definitie: Se numeste graf eulerian, un graf care contine un ciclu eulerian. Exemplul1: Ciclul C=[1,2,3,6,7,8,3,4,5,1] este eulerian, deoarece muchiile sale consecutive sunt distincte doua cate doua (ciclul nu trece de doua ori prin acelasi ciclu).

Exemplul 2:

Pentru acest graf, ciclu C = [2,1,5,2,3,4,2] este eulerian, deoarece pleaca din 2 si se intoarce tot in doi, iar muchiile sale consecutive, adica [2,1], [1,5], [5,2], [2,3], [3,4], [4,2] sunt distincte doua cate doua si reprezinta toate muchiile grafului. Teorema: Un graf fara varfuri izolate este eulerian, daca si numai daca este conex si gradele tuturor varfurilor sunt numere pare.

3.CURIOZITATI Grafuri eulerieneAdeseori suntem tentai s credem ca simplul fapt de a traversa strzi sau poduri nu implic nicio idee deosebit. Iat ns c exist o celebr problem de traversare n care singura idee implicat este aceea de traversare, problema celor apte poduri din Knigsberg. Aceast banal i totui foarte controversat problem a dus la apariia i dezvoltarea teoriei grafurilor. Problema se pune cam aa: Oraul Knigsberg era aezat pe coasta Mrii Baltice, la gurile rului Pregel. Pe ru erau dou insule legate de rmuri i ntre ele de apte poduri ca n figura 1.

Oamenii care cutreierau aceste insule au observat c dac porneau de pe malul sudic al rului, nu puteau s-i planifice plimbarea astfel nct s traverseze fiecare pod o singur dat. Se prea c ori trebuia s sar un pod ori s-l traverseze de dou ori. n anul 1735 Euler a descoperit c nu mai are rost s se ncerce, propunnd urmtoarea analiz a problemei, din punct de vedere matematic: S considerm mai nti insula estic (fig.2.):

sunt trei poduri care duc la ea. Deoarece se pleac de pe malul sudic, nseamn c se pleac din afara insulei estice. Deoarece fiecare din cele trei traversri trebuie efectuate o singur dat, plimbarea trebuies se termine pe insula estic. S considerm acum insula vestic: sunt cinci poduri care duc pe ea, iar cinci este din nou numr impar. Aadar plimbarea ncepe n afara insulei, i deci trebuie s se termine pe insula vestic.

Aceasta nseamn c plimbarea se termin n dou locuri diferite simultan ceea ce e imposibil. Soluia dat de Euler este tipic pentru personalitatea i ingeniozitatea sa. Tot el a scris n anul 1736 prima lucrare de teorie a grafurilor despre problema acestor apte poduri.

Un ciclu al unui graf G care conine toate muchiile lui G se numete ciclu eulerian. Un graf G care are un ciclu eulerian se numete graf eulerian. Un graf G fr vrfuri izolate este eulerian dac i numai dac este conex i gradele tuturor vrfurilor sale sunt numere pare. Din punct de vedere al teoriei grafurilor, problema se pune cam aa: cele patru regiuni (insule i maluri) A,B,C,D i cele apte poduri le reprezentm n graful urmtor (fig.3.):

Muchiile grafului reprezentnd posi-bilitile de trecere de pe un mal pe un pod i reciproc. Problema are soluie dac acest graf conine un ciclu eulerian. Un astfel de ciclu, utilizeaz la fiecare trecere printr-un vrf dou muchii ce nu mai pot fi folosite pentru o nou trecere. Cum fiecare dintre cele patru vrfuri (A,B,C,D) au grade impare, rezult c ultima muchie va rmne nefolosit sau va fi folosit pentru a face trecerea de final ( pentru a ncheia plimbarea). Aceasta ar nsemna c ori va rmne la unul din vrfuri, o muchie nefolosit (fapt ce demonstreaz c nu avem un ciclu eulerian) ori plimbarea ar trebui s se termine n mai multe locuri simultan ceea ce e iari imposibil. Ciclu eulerian: Fiind dat un graf neorientat, s se verifice dac este graf eulerian i n caz afirmativ, s se determine un ciclu eulerian al su.

Explicaia programului: Pornim dintr-un varf neizolat reinut cu ajutorul variabilei prim, n cadrul procedurii de citire, apoi cutm un ciclu eulerian al grafului printr-un algoritm backtracking. Vom folosi pentru reinerea ordinii vrfului n ciclul eulerian un ir s. n cadrul procedurii de cititre a matricii de adiacen, numrm i muchiile grafului cu ajutorul variabilei m. Funcia valid verific dac vrful k aparine ciclului eulerian (dac este adiacent cu vrful anterior determinat, iar n cazul n care este ultimul vrf k=m dac este adiacent cu primul vfr al ciclului). Procedura back caut succesiv, autoapelndu-se, vrfuri adiacente cu vrful anterior determinat pn cnd se ajunge la ultimul vrf al ciclului (k=m); n acest caz, variabila boolean gsit care a fost iniializat pe false, ia valoarea true i este tiprit irul s ncheindu-l cu primul vrf al su (pentru a arta c este un ciclu). Dac nu a fost gsit nici un ciclu eulerian al grafului dat (gsit=false), atunci graful nu este eulerian i se tiprete mesaj. Acelai lucru se ntmpl i dac graful nu are vrfuri neizolate (prim=0). n viaa de zi cu zi rezolvm adesea, fr s ne dm seama probleme de grafuri euleriene, de exemplu cnd vrem s mergem cu trenul n circuit i vrem s pltim mai puin, calculm n aa fel nct s trecem peste tot i s pltim mai puin. Dar aceasta nu o facem numai noi i potaii, ci grafurile se utilizeaz la calcularea poziilor optime de amplasare a sateliilor de comunicaie pentru ca informaia transmis s foloseasc puin timp, cci n noua er :,,time is money.

Grafuri hamiltonieneSe numeste ciclu hamiltonian intr-un graf, un ciclu elementar care contine toate varfurile grafului. Un graf care contine un ciclu hamiltonian se numeste graf hamiltonian. Un lant elementar care contine toate varfurile grafului se numeste lant hamiltonian. * Un graf hamiltonian are cel putin trei varfuri. * Graful complet cu n varfuri este un graf hamiltonian. Teorema: Fie G=(X,U), cu n>=3 varfuri, daca oricare ar fi x un nod al grafului si d(x)>=n/2, atunci graful este hamiltonian. drum hamiltonian: un drum elementar care trece prin toate nodurile grafului; circuit hamiltonian: un circuit care trece prin toate nodurile grafului; n timp, s-au evideniat o multitudine de probleme reductibile la gsirea unui drum (sau circuit) hamiltonian ntr-un graf, cum ar fi: 1. Problema potaului (gsirea traseului cel mai scurt care trece pe la toate locuinele ce aparin de oficiul potal la care lucreaz acesta); 2. Problema adunrii deeurilor (cel mai scurt drum care trece pe la toate punctele de depozitate a deeurilor); 3. Problema succesiunii operaiilor (executarea mai multor operaii pe o main n acea ordine n care suma timpilor consumai cu pregtirea mainii pentru trecerea de la o operaie la urmtoarea s fie minim) 4. Ordinea lipirii unor componente electronice pe o plac, etc;

Determinarea drumurilor hamiltoniene Problema determinrii drumului (circuitului) hamiltonian de valoare optim s-a dovedit deosebit de dificil, neexistnd nici acum un algoritm care s rezolve problema n timp polinomial i nici mcar o metod simpl prin care s se decid dac ntr-un graf dat exist sau nu drumuri hamiltoniene. Exist ns mai muli algoritmi, unii exaci alii heuristici, care reuesc, ntr-un caz sau altul, s rezolve problema satisfctor i n timp util. Teorema: Dac ntr-un graf orientat fr circuite exist un drum hamiltonian atunci acesta este unic. Demonstraie: Deoarece un drum hamiltonian se identific cu o permutare a nodurilor grafului, existena a dou drumuri hamiltoniene implic existena a dou permutri distincte a nodurilor grafului i cum dou permutri distincte difer prin cel puin o inversiune vor exista dou noduri xi i xj n ordinea xi xj pe un drum i invers pe cellalt, existnd deci un drum att de la xi la xj ct i de la xj la xi, cele dou formnd mpreun un circuit, n contradicie cu ipoteza. Graful din figura 1: Este hamiltonian, deoarece ciclul C=[1,2,3,5,4,1] este elementar (pleaca din varful 1 si se incheie tot in 1, iar muchiile [1,2], [2,3], [3,5], [5,4] si [4,1] sunt distincte doua cate doua) si in plus contine toate varfurile.