Gradul- P.D.

Definitie: Gradul unui nod x al grafului G este egal cu numarul muchiilor incidente cu nodul si se noteaza cu d(x).

Terminologie:

• Se numeste nod terminal un nod care are gradul egal cu 1.
• Se numeste nod izolat un nod care are gradul 0

         

            X={1,2,3,4,5,6}
            U={(1,2),(1,6),(2,6),(3,5)}
      nodurile 1 si 2 sunt nodurile vecine nodului 6;
      nodurile 5 si 3 sunt noduri terminale;
      nodul 4 este nod izolat.





Exemplu:

• Multimea nodurilor:  X={1,2,3,4,5,6,7}
• Multimea muchilor: U={(1,2), (2,3), (2,4), (3,4), (5,6)}
• Gradul nodului 2: d(2)=3
• Nodu izolat: 7 
• Noduri terminale:  1, 5, 6 
• Nodurile 2 si 3 se numesc adiacente. La fel nodurile 2 si 4. 
• Nodul 2 si muchia (3,4) se numesc incidente. 

Teoreme:

1.Numarul total de grafuri cu n noduri este:







2.Suma gradelor tuturor nodurilor unui graf neorientat este egala cu dublul numarului de muchii.









3.Daca graful G neorientat are n noduri, n>2, atunci cel putin 2 noduri au acelasi grad.
4.Pentru orice grad neorientat numarul nodurilor de grad impar este par.
5.Numarul minim de muchii pe care trebuie sa le aiba un graf neorientat cu n noduri, ca sa nu existe noduri izolate este:

Se numeste lant intr-un graf neorientat o succesiune de varfuri cu proprietatea ca intre oricare doua varfuri(noduri) alaturate exista o muchie.
Numim lant elementar o succesiune de varfuri care respecta proprietatea de lant si-n care oricare doua varfuri sunt distincte. In caz contrar lantul se numeste neelementar.

Lungimea unui lant reprezinta numarul de muchii/arce din care este format.

• Lantul simplu este lantul care contine numai muchii/arce distincte.
• Lantul compus este lantul care nu este format din muchii/arce distincte.
• Lantul elementar este lantul care contine numai noduri distincte.

Ciclu elementar este un ciclu in care toate nodurile sunt distincte doua cate doua (cu exceptia primului si ultimului nod).
Numim ciclu un lant in care toate muchiile/arcele sunt distincte doua cate doua si primul nod coincide cu ultimul.

Un graf fara cicluri se numeste graf aciclic.

Se numeste graf partial notat cu Gp=(x,v), cu proprietatea ca multimea v de perechi de varfuri este inclusa in multimea x.

 

Imaginea 1 prezinta un graf oarecare iar imaginea 2 prezinta graful partial al primului prin eliminarea muchilor (1,2) si (2,4).
    

Graf complet.Graf Bipartit -G.L

 Graf complet

 

 Definitie

  Fie G = (V, M) un graf neorientat. Graful G se numeste graf complet daca oricare doua varfuri distincte ale sale sunt adiacente.

Observatii:
- Graful complet se noteaza cu Kn (n reprezinta numarul de noduri)
- d(i) = n-1
- intr-un graf Kn exista n(n-1)/2 muchii

EXEMPLU:

 

 

Graful Bipartit 

Definitie:

Un graf G=(X,U) se numeste graf bipartit daca exista 2 multimi nevide A si B astfel incat X= AB si AB=∪∩φ si oricare muchie din U a lu G are o extremitate in A si una in B.

EXEMPLU: 

G=(X,U)

X={1,2,3,4,5,6,7}

U={[1,2];[1,5];[3,5];[3,6];[4,7]}

A={1,3,4}

B={2,5,6,7}

 

              

Observatie:

1) Un  graf bipartit se numeste complet  daca pentru oricare x din A si oricare y din B exista muchia xy.

 
      2) Daca A are p elemente, iar B are q elemente, numarul total de muchii ale unui graf bipariti este p*q.

Ex de problema Subgraf-P.B.

1.Se citesc 2 grafuri neorientate, unul cu n noduri si m muchii, iar celalalt cu k varfuri si l muchii, ambele date prin vectorul muchiilor. Sa se determine daca al doilea graf este subgraf al primului.

int a[100][100],b[100][100],n,m,k,l;
void citire()
{int x,y,i;
f>>n>>m;
for(i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=1;
a[y][z]=1;
}
g>>k>>l;
for(i=1;i<=l;i++)
{g>>x>>y;
b[x][y]=1;
b[y][x]=1;
}
}

int subgraf()
{for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
if(a[i][j]!=b[i][j]) return 0;
return 1;
}

void main()
{citire();
if(subgraf()) cout<<"da";
else cout<<"nu";

Subgraf.Graf partial-P.B.

Definiţie Un graf parţial al grafului G=(V,U) este un graf G1=(V,U1) astfel încât U1este inclus in U, adică G1 are aceeaşi mulţime de vârfuri ca G, iar muţimea de muchii U1 este chiar U sau o submulţime a acesteia (un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de noduri şi eliminând o parte din muchii).

Definiţie Un subgraf al unui graf G=(V,U) este un graf H(V1,U1) astfel încât V1 este inclus in V iar U1 conţine toate muchiile din U care au ambele extremităţi în V1 (un subgraf se obţine eliminând vârfuri din V şi muchiile incidente acestor vârfuri). Vom spune că subgraful H este indus sau generat de mulţimea de vârfuri V1.

Matricea de adiacenta. -P.D.

Matricea de adiacenta este o matrice a cu n linii si n coloane, in care elementele a[i,j] se definesc astfel:

• 1, daca exista muchia [i,j] cu i diferit de j. 
• 0 in caz contrar. 

Lista vecinilor nodului x cuprinde toate nodurile care sunt extremitati ale muchiilor ce trec prin nodul x.

Observatii:

•         Matricea de adiacenta asociatã unui graf neorientat este o matrice simetricã
•          Suma elementelor de pe linia k reprezintã gradul nodului k
•          Suma elementelor de pe coloana k reprezintã gradul  nodului k

Fie graful din figura urmatoare: 

                                                                          
                                 0 1 0 1 0 0           nodul 1 are gradul 2
                                 1 0 1 0 0 0           nodul 2 are gradul 2
                                 0 1 0 1 1 0           nodul 3 are gradul 3
                                 1 0 1 0 0 0           nodul 4 are gradul 4
                                 0 0 1 0 0 0           nodul 5 are gradul 1
                                 0 0 0 0 0 0           nodul 6 are gradul 0       

• Numarul de noduri este 6 si numarul de muchii este 5.
• Matricea este simetrica si patratica avand 6 linii si 6 coloane.
• Diagonala principala contine numai valori nule.

Pentru a prelucra graful se citesc:

6- reprezentand n, numarul de noduri
5- reprezentand m, numarul de muchii
5 perechi x-y reprezentand extremitatile celor 5 muchii:

1-2 => a[1,2]=a[2,1]=1
1-4 => a[1,4]=a[4,1]=1
2-3 => a[2,3]=a[3,2]=1
3-4=>  a[3,4]=a[4,3]=1
3-5 => a[3,5]=a[5,3]=1
 
Matricea de adiacenta este o matrice patratica si simetrica fata de diagonala principala.
 
Exemplu de matrice patratica:

 

                               

Adiacenta. Incidenta. Grad. -P.D

   Reamintim faptul ca un graf neorientat pune in evidenta o relatie simetrica, cum ar fi, de exemplu, cea care exista intre componentele unei retele de calculatoare.
   Varfurile unui astfel de graf (calculatoarele din retea) sunt conectate intre ele prin legaturi de comunicatie directa (muchiile grafului). Intr-o astfel de retea este necesar ca orice calculator sa poata comunica cu toate celelalte calculatoare prezente in retea. De aceea, graful respectiv trebuie sa aiba unele particularitati.
Fie G = (V,U) un graf neorientat in care V={x1,x2,…,xn}.

Definitie Se numeste graf neorientat o pereche ordonată de multimi (V,U), V fiind o multime finita si nevida de elemente numite noduri sau varfuri, iar U o multime de perechi neordonate (submultimi de două elemente) din V numite muchii.

 Definitie Numim muchii adiacente două muchii cu o extremitate comuna. Pentru exemplul de mai sus, muchii [1,5] şi [5,4] sunt muchii adiacente pentru ca au ca extremitate comuna nodul 5. 

 

! Matricea de adiacenta asociata unui graf neorientat este o matrice simetrica.

Adiacenta: Intr-un graf neorientat existenta muchiei (v,w) presupune ca w este adiacent cu v şi v adiacent cu w.

In exemplul din figura, varful 1 este adiacent cu 4 dar 1 şi 3 nu reprezinta o pereche de varfuri adiacente.

Incidenta: o muchie este incidenta cu un nod daca il are pe acesta ca extremitate. Muchia (v,w) este incidenta in nodul v respectiv w.

Grad: Gradul unui nod v, dintr-un graf neorientat, este un numar natural ce reprezinta numărul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv)

In graful de mai jos avem:

1. Nodurile 2 si 3 se numesc adiacente.
2. Nodul 4 este un nod terminal.
3. Pentru nodul 2 putem spune ca 3 reprezinta gradul sau.
4. Muchia (2,5) si nodul 2 se numesc incidente

:)

...cerul from on Vimeo.