Într-un număr mare de situaţii, matematicianul, inginerul, chimistul ca şi psihologul a fost condus la reprezentarea unor cazuri concrete prin desenarea unor puncte pe o foaie de hârtie ( aceste puncte reprezentând numere, localităţi, grupări chimice, indivizi dintr-un grup social, operaţiile unui proiect ) şi prin linii continue care leagă anumite perechi de puncte şi care simbolizează o relaţie, un drum, o legătură chimică, o atitudine sau o preferinţă, o relaţie de succesiune temporală sau o legătură dintre două noduri ale unei reţele electrice.<Scurt istoric>
Aceste puncte au fost numite vârfuri sau noduri, iar liniile care unesc perechile de vârfuri au fost numite arce sau muchii (după cum sunt orientate sau nu).
DEF. 1. Se numeşte graf perechea G = ( X, U ), unde X reprezintă mulţimea vârfurilor grafului iar U este o familie de perechi de vârfuri care formează mulţimea arcelor (sau muchiilor). În continuare vom presupune că graful G este finit, adică mulţimea nodurilor X={x1, x2, …, xn}este finită iar mulţimea muchiilor U={u1, u2,…,um} este tot un şir finit.
Graful din figura de mai sus este un graf neorientat cu n=11 noduri, mulţimea nodurilor este X={1,2,3,...,11} iar mulţimea muchiilor este U={ (1,2), (2,3),...,(9,10)} şi conţine un număr de m=9 muchii.
< Exercitii de construire a unui graf >
DEF.2. Spunem că două noduri i, j ale unui graf sunt adiacente dacă şi numai dacă există muchia u =(i, j) în mulţimea muchiilor U. Spunem că muchia u şi nodul i, respectiv muchia u şi nodul j, sunt incidente. < Mai multe >
DEF.3 Se numeşte grad a nodului i (oricare ar fi i apartinând nulţimii nodurilor X) şi se notează grad(i), numărul de muchii incidente în nodul respectiv.
Pentru graful din fig.1 grad(5)= 4, grad (9)=1, grad(1)=2, grad(11) = 0 ş.a.m.d.
Fie un graf G, cu n noduri atunci:
DEF.4 Se numeşte nod izolat un nod i care are gradul zero.
DEF.5 Se numeşte nod terminal, un nod i care are gradul unu.
DEF.6 Se numeşte nod oarecare un nod i care are gradul strict mai mare decât unu.
Exemplu: Nod izolat: 11
Nod terminal: 6, 7, 8, 9,10
Nod oarecare: 1,2 ,3 ,4 ,5
Răspundeți la următoarele întrebări ! Desenați umătorul graf !
În general, pentru un graf neorientat G=( X, U ) care are n noduri ( notate x1, x2, x3,…, xn) şi m muchii au loc următoarele relaţii importante între gradele nodurilor:
Gradul unui nod poate fi un număr natural cuprins între 0 si n-1 pentru oricare nod xi aparţinând mulţimii nodurilor X
Suma gradelor nodurilor unui graf neorientat este egala cu dublu numărului de noduri, deoarece fiecare muchie contribuie cu câte o unitate la gradele celor două noduri pe care le uneşte:
În orice graf există un număr par de vârfuri de grad impar
Un graf cu n ≥2 noduri conţine cel puţin două noduri cu acelaşi grad
Numărul maxim de muchi pe care îl poate avea un graf neorientat se calculează cu relaţia:
unde n reprezintă numărul de noduri ale grafului.
DEF. 7. Fie G=(X,U) un graf cu n noduri. Graful GS =(A,V) se numeşte subgraf al grafului G (generat sau secţionat de mulţimea de vârfuri A) dacă mulţimea vârfurilor A este inclusă în mulţimea vârfurilor grafului G şi mulţimea arcelor V conţine doar arce ce au ca noduri adiacente doar nodurile mulţimii A. Cu alte cuvinte pentru a obţine un subgraf dint-un graf dat, este suficient să se îndepărteze un anumit număr de vârfuri, precum şi arcele ce le sunt adiacente.
Determinati un subgraf plecand de la un graf dat
DEF 8. Fie G=(X,U) un graf cu n noduri. Graful GP =( Y , V) se numeşte graf parţial al grafului G, dacă Y=X şi mulţimea arcelor grafului GPeste inclusă în mulţimea arcelor grafului. Exemplu de graf partial
Determinati un graf partial plecand de la un graf dat.
DEF.9. G=(X,U) un graf cu n noduri. Graful G este complet dacă orice pereche de vârfuri este legată cu o muchie.Exemplu de graf complet.
DEF. 10 Un graf G=(X,U) se numeşte bipartit dacă există o partiţie a mulţimii nodurilor X=X1UX2, X1 intersectat cu X2 = Ø, astfel încât fiecare muchie a lui G are o extremitate în mulţimea X1 şi cealaltă în X2.