Circuite hamiltoniene - cercetări operaționale

Notiuni fundamentale

In scopul descrierii unor activitati din cadrul unui proces de productie sau a relatiilor existente intre elementele unei structuri organizatorice se pot folosi 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

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

Deoarece, in cele mai multe din cazurile care vor fi analizate in aceasta lucrare, 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.

1. gradul unui nod xk: este suma semigradelor nodului xk: = + ;

2. nod izolat: este un nod cu gradul 0;

3. nod suspendat: este un nod cu gradul 1;

4. arce adiacente: arce care au o extremitate comuna;

5. 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;

6. lungimea unui drum: este numarul arcelor care il formeaza;

7. drum elementar: un drum in care fiecare nod apare o singura data;

8. drum simplu: un drum in care fiecare arc apare o singura data;

9. 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¬)  .

10. drum hamiltonian: un drum elementar care trece prin toate nodurile grafului;

11. drum eulerian: un drum simplu care contine toate arcele grafului;

12. lant: un drum in care arcele nu au neaparat acelasi sens de parcurgere;

13. circuit: un drum in care nodul initial coincide cu cel final;

14. circuit elementar: un drum in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;

15. circuit simplu: un drum in care fiecare arc apare o singura data;

16. circuit hamiltonian: un circuit care trece prin toate nodurile grafului;

17. ciclu: este un circuit in care arcele nu au neaparat acelasi sens de parcurgere;

18. ciclu elementar: un ciclu in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;

19. ciclu simplu: un ciclu in care fiecare arc apare o singura data;

Observatie: Intr-un graf neorientat notiunile de drum si lant sunt echivalente si de asemenea cele de circuit si ciclu.

20. graf partial al unui graf G = (X,U): este un graf G'(X,U') cu U'  U;

21. subgraf al unui graf G = (X,): este un graf G'(X',') unde X'  X si '(xi) = (xi)  X' pentru orice xi  X';

22. 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 .

23. graf tare conex: este un graf in care intre oricare doua noduri exista cel putin un drum;

24. 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;

25. 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