Graf

În disciplina matematică a teoriei grafurilor, un graf este 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/nodurilor) și din linii drepte sau curbe care unesc aceste puncte (care corespund muchiilor sau arcelor).

Se numește ordin al unui graf numărul de noduri al grafului, deci cardinalul mulțimii X(G), și se notează această valoare cu ${\displaystyle |G|}$ . Numărul de muchii se notează cu ${\displaystyle \|G\|}$ .

Graful vid este graful ${\displaystyle G(\emptyset ,\emptyset )}$  și se notează cu ${\displaystyle \emptyset }$ . Se spune că un graf G este trivial dacă acesta are ordinul 0 sau 1.

Un nod v este incident cu o muchie r dacă ${\displaystyle 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.

Se numește grad al unui nod particular v ${\displaystyle (v\in X(G))}$ , numărul de arce care sunt conectate la acel nod și se notează de obicei cu ${\displaystyle \rho (v)}$  sau cu ${\displaystyle d(v)}$ .

Dacă se adună gradele tuturor nodurilor din graful G se obține de două ori numărul de muchii:

${\displaystyle \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ă.

 

Se numește drum într-un graf orientat 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. Se numește 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).

Se spune 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ă.

Un graf este conex dacă între oricare două vârfuri ale acestuia există cel puțin un drum. De exemplu graful din figura 1 nu este conex, în timp ce graful din figura 3 este un graf conex. Graful trivial este considerat conex.

În cazul grafurilor orientate există două noțiuni asociate cu noțiunea generală de conexitate. Un graf orientat este „slab conex” dacă, înlocuindu-i toate arcele cu muchii, transformându-l astfel într-un graf neorientat, graful neorientat astfel obținut este conex (graful din figura 2 este slab conex). Un graf orientat este „tare conex” dacă, oricare ar fi două noduri ale acestuia u și v, există drum și de la u la v, și de la v la u.

Complementul unui graf G este graful ${\displaystyle {\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).

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

• 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
• Tiberiu Ionescu, Grafuri, aplicații, vol. I, Editura Didactică și Pedagogică, București - 1973;
• Alexandru Al. Roșu, Teoria grafelor, algoritmi, aplicații, Editura Militară, București - 1974.

• Algoritmul lui Dijkstra
• Glosar de teoria grafurilor
• Graf chimic

Portal Matematică