Înmatematică șiinformatică,teoria grafurilor studiază proprietățilegrafurilor. Un graf este o mulțime de obiecte (numite noduri) legate între ele printr-o mulțime de muchii cărora le pot fi atribuite orientări (în acest caz, se spune că graful este orientat). Un graf poate fi reprezentatgeometric ca o mulțime de puncte legate între ele prin linii (de obicei curbe).
Dezvoltarea teoriei grafurilor a pornit de la probleme legate de jocuri și amuzamente matematice alcătuite spre a testa ingeniozitatea. Acestea au atras atenția unor matematicieni experimentați caEuler,Hamilton,Cayley,Birkhoff iar cu trecerea anilor teoria grafurilor a devenit un domeniu bogat in rezultate și de o surprinzătoare varietate și aplicabilitate[1].
Grafurile au o importanță imensă îninformatică, de exemplu:
în unele problemele desortare și căutare - elementele mulțimii pe care se face sortarea sau căutarea se pot reprezenta prin noduri într-un graf;
schema logică a unui program se poate reprezenta printr-un graf orientat în care o instrucțiune sau un bloc de instrucțiuni este reprezentat printr-un nod, iar muchiile direcționate reprezintă calea de execuție;
în programarea orientată pe obiecte, ierarhia obiectelor (claselor) unui program poate fi reprezentată printr-un graf în care fiecare nod reprezintă o clasă, iar muchiile reprezintă relații între acestea (derivări, agregări).
