Vizualizare sursă pentru „Graf”

{{altesensuri}}
[[Imagine:Graf neorientat1.png|thumb|200px|Fig. 1 - Graf neorientat.]]
[[Imagine:Graf orientat.png|thumb|200px|Fig. 2 - Graf orientat.]]
În [[matematică]] și mai specific în [[teoria grafurilor]], un '''graf''' (la plural: '''grafuri'''<ref>[[DOOM3]], 2021.</ref>) este o structură care corespunde unui grup de obiecte, în care unele perechi de obiecte sunt într-un anumit sens „legate” reciproc. Obiectele corespund unor abstracții matematice numite într-un graf noduri/vârfuri (numite și puncte) și fiecare legătură dintre perechile de obiecte asociate se numește muchie (numită și arc sau linie, prin care este și reprezentată). De obicei, un graf este reprezentat în formă schematică ca un set/grup de puncte pentru noduri, iar acestea  sunt unite  [[pereche|două câte două]] de [[dreaptă|drepte]] sau [[curbă|curbe]] pentru muchii. Grafurile reprezintă unul dintre obiectele de studiu în [[matematică discretă|matematica discretă]].

Muchiile pot fi orientate/direcționate sau neorientate/nedirecționate. De exemplu, dacă nodurile reprezintă persoane la o petrecere și există o muchie între două astfel de persoane dacă ele își fac cu mâna - își agită mâinile, atunci acest graf este neorientat/nedirecționat, deoarece orice persoană A poate să  agite mâinile spre o persoană B numai dacă B, de asemenea, face cu mâna spre A. În schimb, dacă orice muchie/linie de la o persoană A la o persoană B corespunde admirației față de B a lui A, atunci acest graf este orientat/direcționat, deoarece admirația dintre A și B nu este neapărat reciprocă. Forma anterioară a grafului este denumită graf neorientat/nedirecționat, iar muchiile sunt numite muchii/linii neorientate/nedirecționate, în timp ce ultimul tip de graf este numit grafic orientat/direcționat și muchiile sunt numite muchii orientate/direcționate.

==Definire matematică==
În disciplina [[matematică]] a [[Teoria grafurilor|teoriei grafurilor]], un '''graf''' este o pereche ordonată de [[mulțime|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).

==Ordine și grade==
Se numește ordin al unui graf numărul de noduri al grafului, deci cardinalul [[mulțime|mulțimii]] X(G), și se notează această valoare cu <math>|G|</math>. Numărul de muchii se notează cu <math>\|G\|</math>.

Graful vid este graful <math>G(\empty,\empty)</math> și se notează cu <math>\empty</math>. Se spune că un graf G este <em>trivial</em> dacă acesta are ordinul 0 sau 1. 

Un nod ''v'' este ''incident'' cu o muchie ''r'' dacă <math>v \in r</math>. 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'' <math>(v \in X(G))</math>, numărul de arce care sunt conectate la acel nod și se notează de obicei cu <math>\rho(v)</math> sau cu <math>d(v)</math>.

Dacă se adună gradele tuturor nodurilor din graful G se obține de două ori numărul de muchii:
<div style="text-align:center"><math>\sum _{v \in X(G)} \rho(v) = 2 \cdot |U(G)|</math></div>

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

[[Imagine:Graf complex.png|thumb|300px|Fig. 3 - Graf<br />Vârfurile verzi sunt adiacente.<br />Muchiile roșii formează un drum care leagă nodurile 3 și 6.]]

==Drumuri într-un graf==
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<sub>0</sub>, ..., x<sub>k-1</sub> este un drum în graful G și x<sub>k-1</sub>x<sub>0</sub> este o muchie în acest graf, atunci P + x<sub>k-1</sub>x<sub>0</sub> 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ă.

==Conexitate==
Un graf este ''[[conexitate|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 [[Graf orientat|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 <math>\bar{G}(X,X^2 \setminus U)</math>, 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 ==
* Dacă în definiția unui graf se considera <math>E(G)</math> o [[multimulțime]] pe P<sub>2</sub>(V(G)), adică este dată o funcție m: Ρ<sub>2</sub>(V(G))→ Ν, se obține noțiunea de ''[[multigraf]]''.
* Dacă în definiția unui graf se considera <math>E(G)</math> o multimulțime pe mulțimea părtilor nevide cu cel mult două elemente ale lui <math>V(G)</math>, atunci <math>G</math> se numește ''graf general'' sau ''pseudograf''.

==Note==
<References/>

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

== Vezi și ==
* [[Algoritmul lui Dijkstra]]
* [[Glosar de teoria grafurilor]]
* [[Graf chimic]]
{{Portal|Matematică}}
{{Clase de grafuri}}

[[Categorie:Grafuri| ]]
[[Categorie:Structuri de date]]
[[Categorie:Programare]]