! Observatii

üOrice varf izolat este considerat componenta conexa.

üDaca numarul componentelor conexe dintr-un graf este mai mare decât 1, atunci graful nu este conex.

üUn graf conex are o singura componenta conexa, care cuprinde toate nodurile sale.

üÎn teoria grafurilor, un graf conex este un graf neorientat în care există un drum între oricare două noduri distincte. Un graf neorientat conex ,care are un nod cu proprietatea că dacă acel nod este eliminat (împreună cu muchiile adiacente), graful își pierde proprietatea de conectivitate, se numește

1-conex. Similar, un graf este 2-conex dacă pentru a-i elimina proprietatea de conexitate, este nevoie de eliminarea a două noduri. În general, dacă dintr-un graf conex este nevoie să se elimine un minim de

k noduri (cu muchiile adiacente lor) pentru a obține un graf neconex, acel graf este k-conex.

üNumarul minim de muchii necesare ca un graf neorientat sa fie conex este n-1 ( n=numarul de noduri ) .

üUn graf conex cu n noduri si m-1 muchii este aciclic si maximal in raport cu aceasta proprietate.

üDaca un graf neorientat conex are n noduri si m muchii , numarul de muchii care trebuie eliminate pentru a obtine un graf partial conex , aciclic este (m-n+1).

üDaca un graf are n noduri si m muchii si p componente conexe numarul de muchii care trebuie eliminate pentru a obtine un graf partial aciclic

( arbore) este (m-n+p) .

üPentu a obtine dintr-un graf neorientat conex , 2 componente conexe ,numarul minim de muchii care trebuie eliminate este egal cu gradul minim din graf .

                          Reprezentarea grafurilor neorientate

1.Cu ajutorul matricei de adiacenta(matricei adiacente).

 A є M(m,n),n-nr de varfuri,m-nr de muchii.,unde A(i,j)=1,daca exista muchia (i,j)

                                                                                      0,daca nu exista

OBS! Matricea de adiacenta este simetrica fata de diagonala principala: A(i,j)=A(j,i).

OBS! Gradul unui varf x se poate determina calculand suma pe linia x.

·  Graf partial si subgraf

Def! Fie graful  G=(X,U).Un graf partial al lui G,este un graf G1=(X,V) ,cu V≤U(inclus).Altfel spus ,un graf partial se obtine pastrand toate varfurile si eliminand niste muchii.

Def! Fie graful G=(X,U).Un subgraf al lui G,este un graf S=(Y,T),unde Y≤X si T≤V,iar T va contine numai acele muchii care au ambele extremitati in Y.Altfel spus,un subgraf S al lui G se obtine din G eliminand niste varfuri si odata cu acestea acele muchii care au cel putin o extremitate in submultimea eliminata.

Se numeste graf complet cu n varfuri,notat K indice n (Kn),un graf G=(X,U) cu proprietatea ca oricare doua varfuri sunt adiacente,adica oricare cuplu x,y є X,esista muchia [x,y] є U.

Teorema! Un graf complet  cu n varfuri are n(n-1)/2 muchii.

Definitie!Se numeste graf bipartit ,un graf G=(X,U) cu proprietatea ca exista doua multimi distincte A si B incluse in X,astefel incat:

      -A∩B=multime vida,A+B=X.(+ este reunit);

      -toate muchiile grafului au o extremitate in A si cealalta in B.

Definitie!Se numeste graf bipartit complet ,un graf bipartit cu proprietatea ca pentru orice varf x din A si orice varf y din B , exista muchia [x,y].(A+B=X).

Grafuri neorientate. Probleme propuse

1. Fie un graf neorientat memorat prin matricea de adiacente si o succesiune de k noduri. Sa se determine daca succesiunea citita este un lant din graf
2. Din fisierele mat1.in si mat2.in se citesc doua matrici patratice associate grafurilor g1 si g2. Sa se deremine daca g2 este graf partial pentru g1
3. Fie o harta cu n orase. Cele n orase se citesc din fisier. Intre cele n orase exista m drumuri. Se cunosc distantele celor n drumuri.
1. Sa se determine daca orasul x si orasul y sunt vecine
2. Sa se afiseze lungimile tuturor localitatilor intre care exista drum direct
3. Sa se determine lungimea minima a drumului dintre doua localitati citite de la tastatura
4. La o receptie sunt invitate n personae. Se cunosc numele celor n persoane .  Intre anumite persoane exista relatii de colaborare. Sa se determine daca se pot dispune cele n personae la o masa rotunda astfel incat intre oricare doua personae alaturate sa existe relatii. Se citesc : numele persoanelor si cele m relatiile sub forma de perechi de nume
5. Un eschimos locuieste la iglul cu numarul z. El are o harta pe care sunt marcate iglu-urile din zona (numerotate de la 1 la n) si distantele dintre acestea. Stiind ca din cauza frigului eschimosul nu poate sa parcurga o distanta mai mare de 20 km fara oprire, afisati o varianta de a ajunge  la prietenul lui care locuieste la iglul cu numarul w, eventual cea mai scurta varianta care indeplineste cerinta data. Cati kilometri  a parcurs eschimosul?
6. Un graf neorientat este bipartit daca exista o partitie a multimii nodurilor in doua multimi A si B astfel incat oricare doua varfuri din aceeasi multime sa nu fie adiacente. Sa se scrie un program care verifica daca un graf este bipartit si in caz afirmativ sa se tipareasca multimile A si B
7. Problema colorarii unei harti. Se citesc 4 culori (siruri de caractere) si denumirile a n tari (siruri de caractere) . Sa se coloreze harta astfel incat sa nu existe doua tari alaturate avand aceeasi culoare.  Se va afisa o solutie : tara-culoare, tare-culoare etc.
8. Sa se coloreze un graf astfel incat oricare doua muchii incidente cu acelasi nod sa fie colorate diferit. Care este numarul minim de culori necesar.
9. O pestera are n incaperi, fiecare situata la o adancime h. Configuratia pesterii este data de cele m culoare de acces intre camerele pesterii (culoarele sunt date ca extremitati). In incaperea s exista un izvor de apa sulfuroasa. Se dau n, m, cele m culoare (ca perechi x-y), s si adancimile h ale camerelor. Determinati incaperile inundate si culoarele umezite.
10. Fie un graf neorientat. Sa se determine daca graful contine cicluri.

Descompunerea in componente conexe a unui graf neorientat, dat prin matricea de adiacenta

#include<fstream.h>
int s[20],a[20][20],n,i,j,k;

void df(int nod)
{
int k;
cout<<nod<<" ";
s[nod]=1;
for(k=1;k<=n;k++)
 if((a[nod][k]=1) && (s[k]==0)) df(k);
}

void main()
{
fstream f("graf.txt",ios::in);
f>>n;
while(f>>i>>j) a[i][j]=1;
f.close();
k=1;
for(i=1;i<=n;i++)
 if(s[i]==0)
 {
 cout<<"componenta "<<k<<endl;
 df(i);
 cout<<endl;
 k++;
 }
}

Sa se verifice daca un graf este hamiltonian

Fiind dat un graf neorientat memorat prin matricea de adiacenta sa se determine daca graful este Hamiltonian sau nu.

Notiuni teoretice

Definitie: Se numeste ciclu hamiltonian un ciclu elementar care trece prin toate varfurile grafului.

Definitie: Un graf care admite un ciclu hamiltonian se numeste graf hamiltonian.

#include<fstream.h>

int st[100],n,m,k,a[20][20];

int ns;

int e_valid()

{if(k>1)

if(!a[st[k-1]][st[k]])

return 0;

else

for(int i=1;i<=k-1;i++)

if(st[i]==st[k])

return 0;

if(k==n)

if(!a[st[1]][st[k]])

return 0;

return 1;

}

void afisare()

{for(int i=1;i<=n;i++)

cout<<st[i]<<" ";

cout<<st[1];

k=0;

ns++;

}

void back()

{k=1;

while(k>0)

if(st[k]<n)

{st[k]++;

if(e_valid())

if(k==n)

afisare();

else

{k++;

st[k]=0;}

}

else

k--;

}

void main()

{

fstream f;

f.open("hamiltonian.in",ios::in);

int u,v;

if(f)

cout<<"ok!";

else

cout<<"eroare";

cout<<endl;

f>>n>>m;

for(int i=1;i<=m;i++)

{f>>u>>v;

a[u][v]=a[v][u]=1;

}

cout<<"matricea de adiacenta "<<endl;

for( i=1;i<=n;i++)

{for(int j=1;j<=n;j++)

cout<<a[i][j]<<" ";

cout<<endl;

}

back();

if(ns==0)

cout<<”nu exista solutii”;

}

Graf eulerian

Se da un graf neorintat fara noduri izolate. Sa se determine daca este eulerian. Daca da, sa se afiseze toate ciclurile euleriene care incep cu un nod nd citit de la tastatura.

Notiuni teoretice

Definitie: Un lant care contine fiecare muchie o data si numai o data se numeste lant eulerian. Daca primul varf coincide cu ultimul si lantul este eulerian atunci ciclul se numeste ciclu eulerian.

Definitie: Un graf care contine un cilcu eulerian se numeste graf eulerian.

Teorema: Fie un graf G=(X,U), fara varfuri izolate. Graful G este eulerian daca si numai daca este conex si fiecare varf al sau are gradul par.

#include<fstream.h>

int st[100];

int k,nd; 

int a[10][10],viz[10],n,m;

 void df_r(int nod) 

{int k;

 cout<<nod<<" ";

 viz[nod]=1;

 for(k=1;k<=n;k++)

  if(a[nod][k]&&!viz[k])

     df_r(k);

} 

int valid()

{int x,y;

if(k==1)

   if(st[k]!=nd)

       return 0;

if(k>1)    {x=st[k];

    y=st[k-1];

    if(a[x][y]==0)

        return 0;

    } 

for(int i=1;i<=k-2;i++)

    if((st[i]==x && st[i+1]==y) ||  (st[i]==y && st[i+1]==x))

          return 0; 

 if(k==m)

   if(a[st[m]][st[1]]==0)

          return 0; 

return 1;} 

void tipar()

{for(int i=1;i<=m;i++)

    cout<<st[i]<<"  ";

 cout<<st[1];

 cout<<endl; 

} 

void back()

{ k=1;

 while(k>0)

    {if(st[k]<n)

         {st[k]++;

          if(valid())

              if(k==m)

                 tipar();

              else{k++;

                   st[k]=0;

                   }

            }

     else

           k--;}

} 

 void main()

{ int x,y;

fstream f;

f.open("graf.txt",ios::in);

if(f)

   cout<<"ok";

else

   cout<<"eroare";

f>>n>>m;

for(int i=1;i<=m;i++)

  {f>>x>>y;

     a[x][y]=a[y][x]=1;

     } 

cout<<"matricea de adiac "<<endl;  

for( i=1;i<=n;i++)

 {for(int j=1;j<=m;j++)

  cout<<a[i][j]<<" ";

  cout<<endl;

  } 

 cout<<"nd="; 

 cin>>nd;

 df_r(nd);

 int s=0;

 for(i=1;i<=n;i++)

     s+=viz[i];  

 if(s!=n)

    cout<<"graful nu e conex ";

 else

    {int gasit=0;

     cout<<endl<<"graful e conex!"<<endl;

     for(i=1;i<=n;i++) 

        {s=0;

         for (int j=1;j<=n;j++)

                 s+=a[i][j];

         if(s%2!=0)

              gasit=1;}

         if(gasit)

             cout<<"am noduri fara grade pare";

         else

             cout<<"toate nodurile au gradele pare deci graful e eulerian";

             }

         back();

  }

Definitia grafurilor neorientate.

Definiţie Se numeşte ciclu în G un lanţ L pentru care xi1=xik şi toate muchiile adiacente [xi1, xi2], [xi2, xi3], ..., [xik-1, xik] sunt diferite.

Definiţie Se numeşte ciclu elementar un ciclu care are proprietate că oricare două vârfuri ale sale, cu excepţia primului şi ultimului, sunt diferite două câte două. În caz contrar, ciclul este un ciclu neelementar.

Pentru exemplul anterior un ciclu elementar este [3,5,6,3].

Definiţie Un graf G se numeşte conex dacă pentru orice două vârfuri x şi y diferite ale sale există un lanţ ce le leagă.

Definiţie Se numeşte componentă conexă a grafului G=(V,U) un subgraf G1=(V1,U1), conex, al lui G care are proprietatea că nu există nici un lanţ care să lege un vârf din V1 cu un vârf din V-V1. Cu alte cuvinte, se numeste componenta conexa a unui graf neorientat, G = (V,U), un subgraf al lui G, G1=(V1,U1), conex si maximal.

În exemplul din anterioara avem două componente conexe : 1 : [2]         2 : [1,3,4,5,6]

Definiţie Numarul Mu(G) = m-n+p se numeste numar ciclomatic al grafului G=(V,U); am notat cu m=numarul de elemente din U, n=numarul de elemente din V , p - numarul componentelor conexe ale grafului.

Definiţie Numarul Lm(G) = n-p se numeste numar cociclomatic

Definiţie Un graf bipartit se numeşte complet dacă pentru orice x din A şi y din B, există muchia (x,y).

Fie G=(V,U) un graf neorientat, V={x1,x2,..,xn}.

Definiţie Se numeşte lanţ în G succesiunea de vârfuri L=[xi1,xi2,...,xik] cu proprietate că orice două noduri consecutive din lant sunt adiacente, adică [xi1,xi2], [xi2,xi3], ..., [xik-1,xik]

Definiţie  Dacă vârfurile xi1, xi2, ..., xik sunt diferite două câte două atunci lanţul se numeşte lanţ elementar. În caz contrar, lanţul este lanţ neelemntar. Cu alte cuvinte, un lanţ elementar este un lanţ care nu trece de două ori prin acelaşi vârf.

Definiţie Numim muchii adiacente două muchii cu o extremitate comună. Pentru exemplul de mai sus, muchiile [1,5] şi [5,4] sunt muchii adiacente pentru că au ca extremitate comună nodul 5.

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.

Definiţie Gradul unui vârf x este numărul muchiile incidente cu x. Gradul vârfului x se notează d(x).

Definiţie Un vârf care are gradul 0 se numeşte vârf izolat.

Definiţie Un vârf care are gradul 1 se numeşte vârf terminal.

Propoziţie Dacă un graf G(V,U) are m muchii şi n vârfuri, iar V={x1,x2,...,xn} atunci d(x1)+d(x2)+...+d(xn)=2*m.

Corolar În orice graf G există un număr par de vârfuri cu grad impar.

Definiţie Se numeşte graf complet cu n vârfuri un graf care are proprietatea că orice două noduri diferite sunt adiacente.

Propoziţie Un graf complet Kn are n(n-1)/2 muchii.

Definiţie Un graf G=(V,U) se numeşte bipartit dacă există două mulţimi nevide A, B astfel încât V=A U B, A∩B = şi orice muchie a lui G are o extremitate în A iar cealaltă în B.

Definiţie  Se numeşte graf neorientat o pereche ordonată de mulţimi (V,U), V fiind o mulţime finită şi nevidă de elemente numite noduri sau vâfuri, iar U o mulţime de perechi neordonate (submulţimi de două elemente) din V numite muchii.