Înțelegerea bipartițiilor în teoria grafurilor

În teoria grafurilor, o bipartiție a unui graf este o împărțire a mulțimii sale de vârfuri în două seturi disjunse (numite seturi de partiți), astfel încât toate muchiile conectează vârfurile din seturi de părți diferite. Cu alte cuvinte, nu există muchii între vârfuri în aceeași mulțime de partiți.

De exemplu, luăm în considerare un grafic cu 4 vârfuri {a,b,c,d} și împărțim mulțimea de vârfuri în două părți: {a,b} și {CD}. Graficul este bipartit, deoarece toate muchiile conectează vârfuri din părți diferite.

Bipartiția poate fi utilizată pentru a reduce complexitatea algoritmilor pentru probleme de grafic, cum ar fi traversarea graficului, găsirea căii celei mai scurte și potrivirea graficului.