Graf

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
Pentru alte sensuri, vedeți Graf (dezambiguizare).
Fig. 1 - Graf neorientat
Fig. 2 - Graf orientat

Numim graf o pereche ordonată de mulțimi, notată G=(X,U), unde X este o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar U este o mulțime de perechi (ordonate sau neordonate) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz, graful se numește neorientat, altfel acesta este orientat.

Așadar un graf poate fi reprezentat sub forma unei figuri geometrice alcătuite din puncte (care corespund vârfurilor) și din linii drepte sau curbe care unesc aceste puncte (care corespund muchiilor sau arcelor).

Ordine și grade[modificare | modificare sursă]

Numim ordinul unui graf, numărul de noduri al grafului, deci cardinalul mulțimii X(G), și notăm această valoare cu |G|. Numărul de muchii se notează cu \|G\|.

Graful vid este graful G(\empty,\empty) și se notează cu \empty. Spunem că un graf G este trivial dacă acesta are ordinul 0 sau 1.

Spunem că un nod v este incident cu o muchie r dacă v \in r. Două vârfuri x și y se numesc adiacente dacă există o muchie e care le unește (cu care amândouă vârfurile sunt incidente). Două muchii sunt adiacente dacă există un nod x care să fie incident cu ambele muchii.

Numim gradul unui nod particular v (v \in X(G)), numărul de arce care sunt conectate la acel nod și se notează de obicei cu \rho(v) sau cu d(v).

Dacă adunăm gradele tuturor nodurilor din graful G, obținem de două ori numărul de muchii:

\sum _{v \in X(G)} \rho(v) = 2 \cdot |U(G)|

Faptul că membrul drept al ecuației va fi mereu par, implică aceeași proprietate în membrul stâng, pentru ca egalitatea să fie satisfăcută.

Fig. 3 - Graf
Vârfurile verzi sunt adiacente
Muchiile roşii formează un drum care leagă nodurile 3 şi 6

Drumuri într-un graf[modificare | modificare sursă]

Numim drum într-un graf o succesiune de muchii adiacente și distincte care conectează două vârfuri din graf (numite capetele drumului). Un drum se numește simplu dacă muchiile care îl compun sunt distincte. Numim ciclu un drum care are drept capete un același vârf.

Dacă P = x0, ..., xk-1 este un drum în graful G și xk-1x0 este o muchie în acest graf, atunci P + xk-1x0 este un ciclu din graful G.

Un ciclu se numește hamiltonian dacă este simplu și trece prin toate nodurile grafului G, exact o dată, și se numește eulerian dacă trece prin toate muchiile grafului G, exact o dată. Nu orice graf conține un ciclu hamiltonian (Fig. 2).

Spunem că S este un subgraf al lui G, dacă acesta conține o parte din vârfurile lui G și numai acele muchii care le conectează.

Conexiune[modificare | modificare sursă]

Spunem că un graf este conex dacă între oricare două vârfuri ale acestuia există cel puțin un drum. De exemplu grafurile din figurile 1 și 2 nu sunt conexe, în timp ce graful din figura 3 este un graf conex. Graful trivial este considerat conex.

Complementul unui graf G este graful \bar{G}(X,X^2 \setminus U), care conține o muchie între vârfurile x și y dacă și numai dacă G nu conține o astfel de muchie.

Complementul unui graf care nu este conex, este un graf conex. Reciproca nu este adevărată, de exemplu pentru un lanț de lungime 3 (între 4 vârfuri).

Noțiuni asociate[modificare | modificare sursă]

  • Dacă în definiția unui graf se considera E(G) o multimulțime pe P2(V(G)), adică este dată o funcție m: Ρ2(V(G))→ Ν, se obține noțiunea de multigraf.
  • Dacă în definiția unui graf se considera E(G) o multimulțime pe mulțimea părtilor nevide cu cel mult două elemente ale lui V(G), atunci G se numește graf general sau pseudograf.

Bibliografie[modificare | modificare sursă]

Vezi și[modificare | modificare sursă]