Test de Bipartisme
BFS et 2-coloration
Enonce
Implémenter est_bipartite(G) qui renvoie True si le graphe non orienté est biparti, False sinon.
Tester sur un cycle pair $C_4$ (biparti), un cycle impair $C_5$ (non biparti) et un graphe biparti complet $K_{2,3}$.
Signature attendue
def est_bipartite(G: dict) -> bool:Exemples
est_bipartite({0:[1,3], 1:[0,2], 2:[1,3], 3:[2,0]})→Trueest_bipartite({0:[1,4], 1:[0,2], 2:[1,3], 3:[2,4], 4:[3,0]})→False
📖 Rappel de cours
Un graphe est biparti si on peut partitionner ses sommets en deux ensembles $A$ et $B$ tels que toute arête relie un sommet de $A$ à un sommet de $B$ (jamais deux sommets du même ensemble).
Théorème (König) :
Un graphe est biparti si et seulement si il ne contient aucun cycle de longueur impaire.
Algorithme (BFS / 2-coloration) :
On lance un BFS et on colorie les sommets alternativement avec deux couleurs $0$ et $1$. Si à un moment on découvre un voisin déjà colorié de la même couleur, c'est qu'il existe un cycle impair → pas biparti.
Applications : graphes de relations (employés ↔ projets), problèmes de couplage (mariage stable), planification.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Coloration de Graphe
- Plus Court Chemin dans un Labyrinthe
- Représentations d'un Graphe
- Détection de Cycle (graphe orienté)
- Diamètre d'un Arbre
- Algorithme de Floyd-Warshall
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.