Teoria grafurilor

De la Wikipedia, enciclopedia liberă

In matematica si informatica, teoria grafurilor studiaza proprietetile grafurilor.Un graf este o multime de obiecte (numite noduri) legate intre ele de o multime de muchii carora le pot fi atribuite directii (in acest caz, se spune ca graful este orientat).Vizual, un graf este reprezentat ca o multime de puncte legate intre ele prin linii.

Grafurile au o importanta imensa in informatica.Exemple :

-in problemele de sortare si cautare - elementele multimii pe care se face sortarea sau cautarea se reprezinta prin noduri intr-un graf

-schema logica a unui program se poate reprezenta printr-un graf orientat in care o instructiune sau un bloc de instructiuni este reprezentat printr-un nod, iar muchiile directionate reprezinta calea de executie.

- in programarea orientata pe obiecte, ierarhia obiectelor (claselor ) unui program poate fi reprezentata printr-un graf in care fiecare nod reprezinta o clasa, iar muchiile reprezinta derivari ale obiectelor (claselor)

[modifică] 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
  • Matrici asociate
  • Structuri de date utilizate in reprezentarea (di)grafurilor