}
==

 Grafuri bipartite
Cuplaj maxim, Multime independentă maximală, Suport minim

h2. Grafuri bipartite
 Cuplaj maxim, Multime independentă maximală, Suport minim

Î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

h3. 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ă.