grafuri

Numim graf o pereche ordonată de mulţimi, notată G=(X,U), unde X este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U este o mulţime de perechi (ordonate sau neordonate) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz, graful se numeşte orientat, altfel acesta este neorientat.Aşadar un graf poate fi reprezentat sub forma unei figuri geometrice alcătuite din puncte (care corespund vârfurilor) şi din linii drepte sau curbe care unesc aceste puncte (care corespund muchiilor sau arcelor).
Grafuri neorientate
Se numeste graf neorientat, o pereche ordonata de multimi notata G=(X,U), unde X={x1,x2,...,xn} este o multime finite si nevida de elemnte numite noduri sau varfuri, iar U={u1,u2,...,un} este o multime de perechi neordonate de elemente din X numite muchii. Asadar un neorientat poate fi reprezentat sub forma unei figure geometrice alcatuite din puncte(noduri,varfuri) si linii drepte sau curbe care unesc aceste puncte (muchii,arce). Exemplu: G=(X,U) X={1,2,3,4,5,6,7,8,9,10} U={(1,2);(1,3);(1,5);(2,3);(6,7);(6,10);(7,8);(8,9);(9,10)}
Nod = element al mulţimii V, unde G=(V, E) este un graf neorientat. Muchie = element al mulţimii E ce descrie o relaţie existentă între două vârfuri din V, unde G=(V, E) este un graf neorientat;
Adiacenta: Într-un graf neorientat existenţa muchiei (v,w) presupune că w este adiacent cu v şi v adiacent cu w. Incidenţă = o muchie este incidentă cu un nod dacă îl are pe acesta ca extremitate. Muchia (v,w) este incidentă în nodul v respectiv w. Grad = Gradul unui nod v, dintr-un graf neorientat, este un număr natural ce reprezintă numărul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv) Nod izolat = Un nod cu gradul 0. Nod terminal= un nod cu gradul 1
Graf complet = graf neorientat G=(V,E) în care există muchie între oricare două noduri.
Numărul de muchii ale unui graf complet este: nr*(nr-1)/2.Unde nr este numarul de noduri
graf complet. Nr de muchii: 4x(4-1)/2 = 6
Numim ordinul unui graf, numărul de noduri al grafului, deci cardinalul mulţimii X(G), şi notăm această valoare cu G .