Definitii - grafuri

Definitii - grafuri

Definitie Un graf G este o pereche de forma unde X este este o multime finita numita multimea varfurilor (sau a nodurilor); orice element se numeste varf; este o submultime a lui , multimea perechilor ordonate , , numite arce.

Pentru un arc varful se numeste extremitate initiala (sursa), iar varful extremitate finala (destinatie).

Graful G admite o reprezentare geometrica in plan, obtinuta astfel:

- varfurile se plaseaza in plan in pozitii distincte oarecare.

- fiecare arc se reprezinta printr-o linie ce uneste cele 2 extremitati si pe care se afla sensul de la la

Definitie: O succesiune de arce in care varful terminal al unuia este origine pentru urmatorul se numeste drum.

Definitie: Un drum este simplu daca foloseste un arc o singura data.

Definitie: Un drum este elementar daca nu trece de doua ori prin acelasi varf.

Definitie: Un drum elementar care cuprinde toate varfurile grafului se numeste hamiltonian.

Definitie Numarul arcelor care compun un drum se numeste lungimea acelui drum.

Intr-un graf G, se numeste muchie o pereche de varfuri de varfuri pentru care avem proprietatea ca sau ; muchiile unui graf reprezentat geometric se prezinta ca niste segmente neorientate.

Definitie: Se numeste lant un sir de arce l = cu proprietatea ca oricare arce vecine si au o extremitate comuna pentru orice

Definitie: Un lant care nu-si repeta varfurile se numeste lant ele-mentar, iar un lant care nu-si repeta muchiile se numeste un lant simplu. Numarul de muchii care formeaza un lant se numeste lungimea lantului.

Definitie: Se spune ca un graf este conex daca intre oricare doua varfuri ale sale exista cel putin un lant care sa le lege. In caz contrar graful este neconex. Un graf se numeste tare conex daca intre oricare doua varfuri ale sale exista cel putin un drum.

Definitie: Gradul unui varf sa se noteaza si reprezinta numarul de arce incidente cu x. Gradul interior al unui varf x se noteaza cu si este numarul arcelor de forma

Definitie Se numeste subgraf al grafului un graf obtinut din G prin suprimarea anumitor varfuri si a tuturor arcelor incidente cu acestea. Vom spune ca subgraful este indus sau generat de multimea de varfuri