==

h3. Mulţime independentă maximală

h2. Mulţime independentă maximală

Într-un graf bipartit o mulţime independentă maximală reprezintă o mulţime de noduri astfel încât oricare 2 noduri din mulţime să nu fie legate printr-o muchie iar orice muchie din graf să aiba unul din noduri în mulţimea independentă.
O proprietate interesantă a unei mulţimi independente maximale este aceea că ea este fie o clică maximală fie un subgraf complet în graful complementar.