thumb|Un graf etichetat, cu 6 noduri și 7 muchii În matematică și informatică, teoria grafurilor studiază proprietățile grafurilor. 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 reprezentat geometric 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 ca Euler, Hamilton, Cayley, Birkhoff iar cu trecerea anilor teoria grafurilor a devenit un domeniu bogat in rezultate și de o surprinzătoare varietate și aplicabilitateIoan Tomescu, Ce este teoria grafurilor?, Editura Științifică și Enciclopedică, 1982, p. 5.
Aplicații Grafurile au o importanță imensă în informatică, de exemplu:
în unele problemele de sortare ș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).
Vocabular al Teoriei Grafurilor. Definiția unui graf Variații în definiția unui graf Subgrafuri Operații cu grafuri Clase de grafuri Drumuri și circuite Matrice asociate unui graf Structuri de date utilizate in reprezentarea (di)grafurilor Glosar de teoria grafurilor Graf chimic
Note
Legături externe Mircea Marin, Teoria grafurilor: Introducere (curs, 2020), Universitatea de Vest din Timișoara
Categorie:Matematică Categorie:Teorii *