Graf

În matematică și mai specific în teoria grafurilor, un graf (la plural: grafuri^[1]) 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 două câte două de drepte sau curbe pentru muchii. Grafurile reprezintă unul dintre obiectele de studiu în 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.