Teoria grafurilor

De la Wikipedia, enciclopedia liberă

Î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 direcţii (în acest caz, se spune că graful este orientat). Vizual, un graf poate fi reprezentat ca o mulţime de puncte legate între ele prin linii (de obicei curbe).

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).