Grafuri - conexitate

Grafuri - Conexitate

Definitia 14: Fie graful G=(X,U). numim lant o succesiune de varfuri L=[x1, x2,.,xn] cu proprietatea ca oricare doua varfuri succesive sun adiacente, adica [x1,x2]IU, [x2,x3] IU,.,[xp-1,xp] IU. varfurile x1 si xp se numesc extremitatile lantului, iar numarul de muchii ce il compun se numeste lungimea lantului.

Definitia 15: Daca varfurile x1,x2,.,xp sunt distincte doua cate doua, lantul se numeste lant elementar. In caz contrar, lantul se numeste lant neelementar.

Definitia 16: Daca intr-un lant, toate muchiile sunt diferite intre ele, lantul se numeste simplu, in caz contrar lantul se numeste compus.

Definitia 17: Daca varfurile x1 si xp coincid, lantul se numeste ciclu. Daca un ciclu are o lungime para, el se numeste par; daca are o lungime impara, se numeste impar.

Definitia 18: Daca toate varfurile unui ciclu sunt distincte, cu exceptia primului si a ultimului, atunci ciclu se numeste ciclu elementar.

Definitia 19: Un graf se numeste conex daca oricare ar fi doua varfuri x si y, exista un lant ce le leaga.

5. Grafuri hamiltoniene

Definitia 20: Fie graful G(X,U). Daca exista un lant elementar care contine toate varfurile grafului, lantul se numeste lant hamiltonian.

Definitia 21: Daca intr-un lant hamiltonian varful initial si varful final coincid, lantul se numeste ciclu hamiltonian, iar graful ce contine un ciclu hamiltonian se numeste graf hamiltonian.

Termenul de ciclu hamiltonian a fost folosit pentru prima data in anul 1857 de William Hamilton, important matematician al epocii, inventatorul unui joc numit jocul icosian. Acesta consta in gasirea unui ciclu hamiltonian care sa uneasca cele 20 de varfuri ale unui dodecaedru, confectionat initial din lemn, cu cate un cui cu o floare la fiecare colt, deplasarea facandu-se numai pe muchii.

O problema devenita clasica ce foloseste notiunea de ciclu hamiltonian este aceea numita problema voiajorului comercial. Aceasta are urmatoarea formulare: "un comis voiajor trebuie sa-si prezinte produsele in mai multe orase. Cunoscand costul deplasarii intre localitatea, se doreste stabilirea unui traseu astfel incat sa ajunga in toate localitatile, insa costul calatoriei sa fie minim". Evident, fiecare localitate poate fi vizitata o singura data, iar la sfarsit, voiajorul comercial revine in punctul de plecare

Folosind termenii teoriei grafurilor, problema revine la determinarea unui ciclu hamiltonian in graful kn, ale carui varfuri reprezinta cele n localitatea, pentru care suma costurilor muchiilor sale este minima.

Pentru a stabili o legatura intre notiunile de graf complet si graf hamiltonian, prezentam urmatoarea teorema:

Teorema: Greful complet kn este hamiltonian.

Teorema: Daca graful G=(X,U) este un graf cu n 3 varfuri, astfel incat gradul fiecarui varf xIX satisface conditia:

d(x) n/2

atunci G este hamiltonian.