Bella at 10:01, 24 February 2020

2020-02-24T10:01:47Z

New page

= Graf Bipartit =
'''Definiţie:''' Un graf G=(X, U) se numește graf bipartit dacă există două mulţimi nevide A și B astfel încât X=A ∪ B, A ∩ B = ∅ şi orice muchie u a lui G are o extremitate în A iar cealaltă în B. Mulţimile A şi B formează o partiţie a lui X.

Exemplu: Graful următor este bipartit. A={1,2,5,7} și B={3,4,6}.

[[image:graf-bipartit.png]]

'''Observatii:'''
* orice arbore este bipartit
* nu orice graf bipartit eate arbore.
'''Definiție:''' Un graf bipartit G=(X,U) se numește bipartit complet dacă pentru oricare două vârfuri x∈A și y∈B, există în graf muchia (x,y); adică (x,y)∈U.

Exemplu: Graful următor este bipartit complet.

[[image:graf-bipartit-complet.png]]

== Verificarea unui graf bipartit ==
Putem verifica daca un graf e bipartit in 2 moduri:
* un graf e bipartit daca putem colora nodurile cu 2 culori, astfel incat fiecare muchie sa aiba capete de culori diferite
* un graf e bipartit daca nu contine cicluri de lungime para;

[[image:bipartitegraph5.jpg|220px]]
[[image:bipartitegraph6.jpg|200px]]

=== Folosirea Metodei Backtracking ===
=== [https://www.pbinfo.ro/?pagina=probleme&id=472 Bipartit1] ===
Vom Utiliza metoda backtracking pentru a genera toate modalitatile de partitionare a celor n noduri.
Vom folosi o stiva pentru a construi o solutie de dimensiune n. Pe stiva vom putea pun doar valori din multimea {1,2}. validarea unei solutii partiale consta in validarea unei valori noi adaugate pe nivelul curent k. Aceasta trebuie sa indeplineasca urmatoarea conditie:

* culoarea nodului k ( 1 sau 2 ) trebuie sa fie diferita de culorile vecinilos sai deja colorati.
<syntaxhighlight>
#include <fstream>
#include <iostream>

using namespace std ;

ifstream fin ( "bipartit1.in" ) ;
ofstream fout ( "bipartit1.out" ) ;

int a[102][102], st[102];
int n, m;
int sol = 0 ;

void afisare (){
if ( sol ){
fout << "DA\n" ;
for ( int i = 1 ; i <= n ; i++ )
if ( st[i] == 1 )
fout << i << " " ;
fout << "\n" ;
for ( int i = 1 ; i <= n ; i++ )
if ( st[i] == 2 )
fout << i << " " ;
}
else
fout << "NU";
}
// e valida colorarea nodului k daca vecinii sai deja colorati au luloare diferita de el
int valid ( int k ){
for ( int i = 1 ; i < k ; i++ )
if ( st[i] == st[k] && a[i][k] == 1 )
return 0;
return 1;
}

void back ( int k ){
if ( k == n + 1 ){
sol++;
return;
}
for ( int i = 1 ; i <= 2 && !sol ; i++ ){
st[k] = i ;
if ( valid ( k ) )
back ( k + 1 ) ;
}
}
int main (){
fin >> n >> m ;
for ( int i = 0; i < m ; i++ ){
int x , y ;
fin >> x >> y;
a[x][y] = a[y][x] = 1 ;
}
back ( 1 ) ;
afisare();
return 0 ;
}
</syntaxhighlight>

=== Folosirea BFS ===
====[https://www.pbinfo.ro/?pagina=probleme&id=1318 bipartit1mare]====
Complexitatea de timp e aceeasi cu a algoritmului BFS. In implementarea de mai jos, unde parcugem vecinii memorati intr-o matrice de adiacenta vom avea complexitatea '''O(n^2)''' unde n e numarul de noduri. Complexitatea deriva din faptul ca pentru fiecare nod i din multimea celor n, parcurg toatea nodurile de la 1 la n pentru a verifica care noduri sunt vecine cu nodul i. Daca vom reprezenta graful folosind liste de adiacenta vom avea complexitate '''O(n+2m)''', unde n e numarul de noduri iar m numarul de muchii. In listele de adiacenta, parcurgem doar nodurile vecine asociate fiecarui nod. Vom avea 2m vecinatati memorate ( o muchia intre x si y este marcata si in lista lui x si in lista lui y).

<syntaxhighlight>
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("bipartit1.in");
ofstream fout("bipartit1.out");

int n, m, i, j, x;
int a[1001][1001];
int c[1001]; // coada in care tin nodurile in ordinea vizitarii lor
int cul[1001]; // marchez daca am vizitat un nod; cand il vizitez il colorez cu 1 si -1

bool BFS( int start, int culoare ){ // pornim parcurgerea de la un nod dat
int i = 1;
int vf = 0;
cul[start] = culoare; //** // marchez ca vizitat nodul start
c[++vf] = start; // punem in coada nodul de la care pornim
while( i <= vf ){ // cata vreme mai am elemente in coada
int nod = c[i]; // nodul curent
//out << nod << " "; // afisez nodul curent
for(int vecin = 1; vecin <= n; vecin++ ) // parcurg toti vecinii nodului curent
if( a[nod][vecin] == 1 )
if( cul[vecin] == 0 ){ // daca nu e colorat
cul[vecin] = -cul[nod]; //** // colorez diferit fata de nod
c[++vf] = vecin; // ii pun in coada
}
else if( cul[vecin] == cul[nod] ) //** // daca am dat de un vexin deja colorat cu aceeasi culoare cu nod
return 0; // graful nu e bipartit
i++; // trec la urmatorul element din coada
}
return 1;
}

int main(){
fin >> n >> m ;
for( int l = 1; l <= m; l++ ){
fin >> i >> j;
a[i][j] = a[j][i] = 1;
}
int p = 1;
for( int i = 1; i <= n; i++ )
if ( cul[i] == 0 && p )
p = (p && BFS( i, 1 )); // apelam bfs pentru fiecare componenta conexa
if( p ){ // daca toate componentele au putut fi colorate
fout << "DA\n"; // graful e bipartit
for( int i = 1; i <= n; i++ ) // afisam nodurile colorate cu 1 ( prima multime )
if ( cul[i] == 1 )
fout << i << " ";
fout << "\n";
for( int i = 1; i <= n; i++ ) // afisam nodurile colorate cu -1
if ( cul[i] == -1 )
fout << i << " ";
}
else
fout << "NU";
return 0;
}
</syntaxhighlight>

=== Folosirea DFS ===
====[https://www.pbinfo.ro/?pagina=probleme&id=1318 bipartit1mare]====
<syntaxhighlight>
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("bipartit1mare.in");
ofstream fout("bipartit1mare.out");

int n, m, i, j;
int a[1001][1001];
int cul[1001]; // marchez daca am vizitat un nod; cand il vizitez il colorez cu 1 si -1
int ok = 1;
void dfs( int nod, int culoare ){
//out << nod << " "; // afisam nodul curent
cul[nod] = culoare; // marcam nodul curent ca fiind vizitat, colorat
for ( int i = 1; i <= n; i++ ) // parcurgem toti vecinii nodului curent
if (a[nod][i] == 1 ){
if(cul[i] == 0 ) // daca nodul nu este vizitat
dfs( i, -culoare ); // il colorez complementar nodului curent
else
if( cul[nod] == cul[i] ) // daca a mai fost vizitat, verific sa nu fie colorat la fel ca nodu lcurent
ok = 0; // in acest caz graful nu e biparti
}
}

int main(){
fin >> n >> m ;
for( int l = 1; l <= m; l++ ){
fin >> i >> j;
a[i][j] = a[j][i] = 1;
}
int p = 1;
for( int i = 1; i <= n; i++ )
if ( cul[i] == 0 ){
ok = 1;
dfs( i, 1 );
p = ( p && ok );
}

if( p ){ // daca toate componentele au putut fi colorate
fout << "DA\n"; // graful e bipartit
for( int i = 1; i <= n; i++ ) // afisam nodurile colorate cu 1 ( prima multime )
if ( cul[i] == 1 )
fout << i << " ";
fout << "\n";
for( int i = 1; i <= n; i++ ) // afisam nodurile colorate cu -1
if ( cul[i] == -1 )
fout << i << " ";
}
else
fout << "NU";
return 0;
}
</syntaxhighlight>

Clasa a XI-a lecția 17 - Revision history

Bella at 10:01, 24 February 2020