}
==

 Grafuri bipartite
Cuplaj maxim, Multime independentă maximală, Suport minim
 
 
 
 
 
Un graf bipartit este un graf G = (V, E) în care mulţimea V poate fi partiţionată în două mulţimi, V1 şi V2 astfel încât orice muchie (u, v) C E implică fie că u C V1 şi v  C V2 fie că u C V2  şi v C V1. Cu alte cuvinte, toate muchiile merg de la mulţimea V1 la mulţimea V2 sau invers.
 
Proprietăţile grafurilor bipartite sunt:
1.	G este 2-colorabil (adică nodurile pot fi colorate în 2 culori astfel încât orice muchie sa aiba noduri colorate diferit)
2.	G nu are cicluri de lungime impară
 
În grafurile bipartite anumite probleme care erau NP pe grafuri normale, se pot rezolva în timp polinomial. Exemple de astfel de probleme sunt: cuplaj maxim, mulţime independentă maximală şi suport minim.
 
Cuplaj Maxim
 
Fiind dat un graf neorientat G = (V, E),  un cuplaj este o submulţime de muchii M astfel încât pentru toate vârfurile v  C V, există cel mult o muchie în M incidentă în v. Spunem că un vârf v C V este cuplat de cuplajul M dacă există cel mult o muchie în M incidentă în v; altfel spunem ca v este neconectat. Un cuplaj maxim  este un cuplaj de cardinalitate maximă.
 
În imagine: un graf bipartit G = (V, E) cu partiţia vârfurilor V = L U R. (a) Un cuplaj de cardinalitate 2. (b) Un cuplaj maxim de cardinalitate 3.
 
Pentru a determina cuplajul maxim vom transforma graful bipartit într-o reţea de transport adaugând un nod sursa (s)si un nod destinaţie (t) şi vom pune capacitate 1 pe toate muchiile.
 
Reţeaua de transport corespunzătoare grafului de mai sus:
 
 
Cuplajul maxim va fi chiar fluxul maxim în această reţea. Nu ne rămâne decât să rulăm unul din algoritmii cunoscuţi precum Edmonds-Karp, Dinic… Complexitatea obţinută va fi O(V *  E) deoarece orice cuplaj în graful bipartit are cardinalitate cel mult min(V1, V2).
 
Un algoritm performant pentru determinarea cuplajului maxim este Algoritmul Hopcroft-Karp. Acest algoritm în loc să determine un singur drum de ameliorare la fiecare pas, el determină un numar maximal (nu neapărat maxim) de drumuri distincte. Astfel se poate demonstra că numarul de paşi necesari este cel mult sqrt(V) . Prin urmare complexitatea va deveni O(E*sqrt(V)).