Conex-bipartit

Enunt

În fişerul text graf.in este memorat un graf neorientat conex astfel:

• pe prima linie un număr natural n, care reprezintă numărul de noduri ale unui graf neorientat.

• pe următoarele linii sunt memorate câte două numere naturale care reprezintă muchiile grafului.

Scrieţi un program care să determine dacă graful dat este bipartit.

(Definiţie:Un graf G=(X,U) se numeşte bipartit dacă există o partiţie a mulţimii nodurilor X=X₁UX₂, X_{1 intersectat cu} X₂ = Ø, astfel încât fiecare muchie a lui G are o extremitate în mulţimea X₁ şi cealaltă în X_2.Detalii suplimentare...)

Exemplu:

Rezolvare: Ideea de rezolvare are la baza un algoritm de parcurgere a grafurilor neorientate. Vom folosi în continuare algoritmul de parcurgere în lăţime. Astfel vom marca alternativ nodurile vizitate ale grafului astfel:

• dacă nodul din prima poziţie din coadă are valoarea 1, atunci toate nodurile adiacente cu el şi nevizitate vor fi marcate cu 2

• dacă nodul din prima poziţie din coadă are valoarea 2, atunci toate nodurile adiacente cu el şi nevizitate vor fi marcate cu 1

La sfârşit vom verifica în vectorul v, dacă între nodurile marcate cu acelaşi număr exista muchie. În cazul în care vom găsi cel mult o pereche de noduri x,y care sunt marcate cu aceiaşi etichetă ( v[x]=v[y] ) şi între nodul x şi nodul y există muchie ( a[x][y]=1 ) atunci putem spune cu certitudine că graful nu este bipartit.

Programul C++ este:

#include<iostream>

#include<fstream>

using namespace std;

int a[20][20],c[20],v[20],ns,n,comp;

int prim;

int ultim;

// citirea grafului din fisier text si construirea matricei de adiacenta

void citire(int a[20][20], int &n)

{ ifstream f("graf.in");

int x,y;

f>>n;

while(f>>x>>y)

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

f.close();

}

// afisarea pe ecran a matricei de adiacenta

void afisare(int a[20][20],int n)

{ cout<<"Matricea de adiacenta este : "<<endl;

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

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

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

cout<<endl;

}

}

// returnează primului nod nevizitat

int exista_nod_nevizitat(int v[20], int n)

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

if(v[i]==0)

return i; // primul nod nevizitat

return 0; // nu mai exista noduri nevizitate

}

// parcurgerea în latime a unei componente conexe, plecând din nodul de start ns

void parcurgere_latime(int a[20][20], int n,int ns)

{ comp++;

v[ns]=1;

prim=ultim=1;

c[ultim]=ns;

while(prim<=ultim)

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

if(a[c[prim]][i]==1)

if(v[i]==0)

{ ultim++;

c[ultim]=i;

if (v[c[prim]]==1)

v[i]=2;

else

v[i]=1;

}

prim++;

}

}

//verific daca graful este bipartit

int bipartit(int v[20],int n)

{

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

for(int y=x+1;y<=n;y++)

if(v[x]==v[y])

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

return 0;

return 1;

}

// functia principala main()

int main()

{ citire(a,n);

afisare(a,n);

ns=1;

parcurgere_latime(a,n,ns);

if (bipartit(v,n))

cout<<"Graf BIPARTIT! ";

else

cout<<"Graful NU este BIPARTIT! ";

return 0;

}