Definiții și proprietăți generale

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

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.

graf1

 

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.

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

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

În general, pentru un graf neorientat G=( X, U ) care are n noduri ( notate x1, x2, x3,…, xn) şi 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. 

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.

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.

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s