CAP.1. DEFINITII SI PROPRIETATI GENERALE

Intr-un numar mare de situatii, matematicianul, inginerul, chimistul ca si psihologul a fost condus la reprezentarea unor cazuri concrete prin desenarea unor puncte pe o foaie de hartie ( aceste puncte reprezentand numere, localitati, grupari chimice, indivizi dintr-un grup social, operatiile unui proiect ) si prin linii continue care leaga anumite perechi de puncte si care simbolizeaza o relatie, un drum, o legatura chimica, o atitudine sau o preferinta, o relatie de succesiune temporala sau o legatura dintre doua noduri ale unei retele electrice.

Aceste puncte au fost numite varfuri sau noduri, iar liniile care unesc perechile de varfuri au fost numite arce sau muchii (dupa cum sunt orientate sau nu).

DEF. 1. Se numeste graf perechea G = ( X, U ), unde X finita si nevida reprezinta multimea varfurilor grafului iar U este o familie de perechi de varfuri care formeaza multimea arcelor (sau muchiilor).

Numarul de elemente ale multimii X se numeste ordinul grafului G iar numarul de elemente ale multimii U se numette dimensiunea grafului.

In continuare vom presupune ca multimea X= x₁, x₂, . , x_n este finita iar U= u₁, u₂, . ,u_m

Fig.1.1 Graf neorientat

Graful din fig. 1 este un graf neorientat care are n=11 noduri, deci multimea nodurilor este X= si are m=9 muchii deci multimea arcelor este U= . In continuare vom nota cu n numarul de noduri si cu m numarul de muchii ale unui graf.

Numarul maxim de muchii pe care il poate avea un graf neorientat este unde n reprezinta numarul de noduri. Pentru a putea forma toate grafurile neorientate cu n noduri trebuie considerate pe rand toate submultimile de muchii din multimea totala de . Numarul de astfel de submultimi este egal cu 2= 2 care reprezinta numarul maxim de grafuri cu n noduri. Asemanator se determina ca numarul maxim de grafuri orientate este egal cu 2n(n-1).

DEF.2. Spunem ca doua noduri i, j ale unui graf sunt adiacente numai si numai daca exista muchia u =(i, j) in multimea muchiilor U, iar u si i, respectiv u si j, sunt incidente.

DEF.3. Daca iIX, atunci multimea N_G (i)= se numeste vecinatatea varfului i in G.

DEF.4. O multime independenta de varfuri sau multime stabila in G este o multime S X de varfuri neadiacente doua cate doua. Cardinalul maxim al unei multimi stabile se numeste numarul de stabilitate sau numarul de independenta al grafului G si se noteaza a(G) .

DEF.5. O multime independenta de muchii sau cuplaj in graful G este o multime de muchii neadiacente doua cate doua. Cardinalul maxim al unei multimi independente de muchii in G se numeste numarul de muchie independenta al grafului G si se noteaza g(G).

In graful de mai sus,

X si

U=

Observam ca in acest graf, multimea de varfuri este stabila si este de cardinal maxim, deci a(G)=4; multimea de muchii formeaza un cuplaj de cardinal maxim, deci g(G)=5.

Analiza: Simboluri chimice - element chimic se numeste simbol chimic Referat: Determinarea energiei de activare Arrhenius - reactia tiosulfatul de sodiu cu acidul sulfuric

DEF.6 Doua grafuri G1=(X1,U1) si G2=(X2,U2) se numesc izomorfe si notam G1 G2 daca exista o bijectie intre multimile lor de varfuri care induce o bijectie intre multimile lor de muchii, adica daca exista o bijectie j X1 X2 cu proprietatea ca aplicatia y U1 U2 definita pt. orice (u,v)IX1 prin y(u,v)= j(u) j(v) este o bijectie.

DEF.6 Se numeste grad ( valenta) a nodului i, iI 1, n si se noteaza grad( i ), numarul de muchii incidente in nodul respectiv.

Pentru graful din fig.1.1 grad( 5 )= 4, grad ( 9 )= 1, grad(1)=2, grad(11) = 0 s.a.m.d.

Fie un graf G, cu n noduri atunci:

DEF.7 Se numeste nod izolat un nod i, iI 1, n care are gradul zero.

DEF.8 Se numeste nod terminal ( pendant) , un nod i, iI 1, n care are gradul unu.

DEF.9 Se numeste nod oarecare un nod i, iI 1, n care are gradul strict mai mare decat                unu.

Exemplu( pentru graful din fig. 1.1)

Nod izolat: 11

Nod terminal: 6, 7, 8, 9,10

Nod oarecare: 1,2 ,3 ,4 ,5

In general, pentru un graf neorientat G=( X,U ) care are n noduri ( notate x₁, x₂, x₃, . , x_n) si m muchii au loc urmatoarele relatii importante intre gradele nodurilor:

grad(x_i) n-1 , i = ;

= 2m, unde i = , deoarece fiecare muchie contribuie cu cate o unitate la gradele celor doua noduri pe care le uneste;

o consecinta interesanta din relatia de mai sus este: in orice graf exista un numar par de varfuri de grad impar;

Un graf cu n 2 noduri contine cel putin doua noduri cu acelasi grad

Daca arcele unui graf au asociate sensuri de parcurgere atunci vom spune ca graful G este orientat iar in caz negativ spunem ca graful este neorientat. In cazul grafurilor neorientate arcul dintre nodul i si nodul j este acelasi cu arcul dintre nodul j si nodul i si se noteaza (i, j) iar la grafurile orientate se stabileste pentru fiecare arc cate un sens de parcurs si deci arcul ( i, j ) nu mai este identic cu arcul ( j, i ).

In cazul grafurilor orientate gradul unui nod este dat de suma dintre semigradul exterior al nodului si semigradul interior.

Se numeste semigrad exterior al nodului i numarul de arce care "pleaca" din nodul i si se noteaza grad⁺( i ).

Se numeste semigrad interior al nodului i numarul de arce care "intra" din nodul i si se noteaza grad^-( i ).

grad( i )= grad⁺( i )+ grad^-( i )

In cazul grafurilor orientate exista urmatoarea relatie:

Fig.1.2 Graf orientat

Exemplu:

pentru nodul 1 gradul este 3:       semigradul exterior este 2

semigradul interior este 1

pentru nodul 3 gradul este 5: semigradul exterior este 2

semigradul interior este 3

pentru nodul 4 gradul este 1:       semigradul exterior este 0

semigradul interior este 1

pentru nodul 6 gradul este 1:       semigradul exterior este 1

semigradul interior este 0

DEF. 10. Fie G=(X,U) un graf cu n noduri. Graful G_S =(A,V) se numeste subgraf  al grafului G (generat sau sectionat de multimea de varfuri A) daca multimea varfurilor A este inclusa in multimea varfurilor grafului G si multimea arcelor V contine doar arce ce au ca noduri adiacente doar nodurile multimii A. Cu alte cuvinte pentru a obtine un subgraf dint-un graf dat, este suficient sa se indeparteze un anumit numar de varfuri, precum si arcele ce le sunt adiacente.

DEF 11. Fie G=(X,U) un graf cu n noduri. Graful G_P =( Y , V) se numeste graf partial al grafului G, daca Y=X si multimea arcelor grafului G_P este inclusa in multimea arcelor grafului G.

a) Graful G        b) Subgraf a lui G c) Graf partial a lui G

Fig.1.3

DEF.12. G=(X,U) un graf cu n noduri. Graful G este complet daca orice pereche de varfuri este legata cu o muchie. In cea ce priveste grafurile orientate, spunem ca este complet daca intre oricare doua noduri x si y exista fie un arc de la x la y, fie un arc de la y la x, fie ambele arce, deci pentru fiecare pereche dintre cele perechi posibile de noduri, exisa trei posibilitati ca aceste noduri sa fie adiacente. Deci exista 3= 3 grafuri complete cu n varfuri.

DEF.13 . G=(X,U) un graf cu n noduri. Graful G este simetric daca oricare doua noduri adiacente sant legate prin doua arce orientate opus unul celuilalt.

DEF.14. G=(X,U) un graf cu n noduri. Graful G este antisimetric daca oricare doua noduri adiacente se leaga intr-o singura directie

a) Graf complet                                  b) Graf simetric c) Graf antisimetric

Fig.1. 4

DEF. 15. Se numeste graf turneu un graf orientat pentru care intre oricare doua varfuri exista doar un singur arc (intr-un sens sau altul). Folosind acelasi rationament ca si in cazul grafurilor complete, deducem ca exista 2 grafuri turneu cu n varfuri.

Grafurile turneu au urmatoarele proprietati care sunt foarte usor de dedus:

grad⁺(i)+grad^-(i) = n-1, i = ;

DEF. 16. Un graf G=(X,U) se numeste bipartit daca exista o partitie a multimii nodurilor X=X₁UX₂, X₁ X₂ = Ø astfel incat X₁ si X ₂ sunt independente si nevide (fiecare muchie a lui G are o extremitate in multimea X₁ si cealalta in X₂ ) _.

Fig.1.5 Graf bipartit

DEF. 17. Se numeste graf ponderat un graf orientat sau nu in care fiecarei muchii i s-a asociat un cost dat, de obicei, o functie de cost f: U

10

17 100 20 Fig.1.6 Graf orientat ponderat

12

DEF. 18. Graful orientat G₁=(X,U₁) se numeste graful transpus al grafului G daca G₁ se obtine din graful G prin inversarea sensului arcelor sale.

a) graful G                                 b) Transpusul grafului G

Fig. 1.7