grafurilor

Grafurile sunt structuri matematice discrete formate dintr-un set de vârfuri (noduri) V și un set de muchii E, care conectează perechi de vârfuri. Dacă muchiile nu au direcție, grafurile sunt neorientate; dacă au direcție, grafurile sunt orientate (arce). Un graf poate fi ponderat, greutatea fiind atribuită fiecărei arce sau fiecărei muchii.

În grafuri, gradul unui vârf este numărul de muchii incident, iar pentru grafurile orientate se vorbește de gradul de intrare (in-degree) și gradul de ieșire (out-degree). O cale este o secvență de vârfuri conectate prin arce sau muchii; un ciclu este o cale care se întoarce la vârful de pornire. Grafurile pot fi conectate (există cale între oricare două vârfuri) sau au mai multe componente.

Clasificări importante ale grafurilor includ grafuri simple (fără bucle și fără muchii multiple între aceleași perechi de vârfuri), grafuri complete (K_n), grafuri bipartite, grafuri planare și grafuri orientate. Arborele este un graf conectat fără cicluri; în versiunile orientate, termenii pot include arbori orientați. În anumite contexte, se folosesc multigrafuri (cu mai multe arce între același vârfuri) sau pseudogrefuri (cu bucle).

Utilizări majore ale grafurilor includ modelarea rețelelor de calcul, a rutelor de transport, a rețelelor sociale și a proceselor biologice sau a fluxurilor de date. Algoritmi importanți în lucrul cu grafuri includ parcurgerea în adâncime (DFS), parcurgerea în lățime (BFS), determinarea celui mai scurt drum (Dijkstra) și identificarea componentelor conexe. Grafurile oferă un cadru general pentru reprezentarea și analizarea relațiilor complexe între obiecte.