Graf

De la Wikipedia, enciclopedia liberă

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 numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz, graful se numeşte orientat, altfel acesta este neorientat.

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

[modifică] Ordine şi grade

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 $ρ(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ă. Suma tuturor termenilor $ρ(v)$ impari trebuie să fie o sumă al unui număr par de termeni, pentru a fi pară. Astfel deducem că orice graf are un număr par de noduri al căror grad este impar.

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

[modifică] Drumuri într-un graf

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 = x₀, ..., x_k-1 este un drum în graful G şi x_k-1x₀ este o muchie în acest graf, atunci P + x_k-1x₀ 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ă.

[modifică] Conexiune

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

[modifică] Bibliografie

Reinhard Diestel - Graph Theory (Electronic Edition 2000)
- Softcover - ISBN 0-387-98976-5
- Hardcover - ISBN 0-387-95014-1
Robert Sedgewick - Algorithms ISBN 0-201-06672-6

Adus de la "http://ro.wikipedia.org../../../g/r/a/Graf.html"

Categorie: Teoria grafurilor