Exercices de programmation pour classes préparatoires
Ecrire une fonction est_biparti(graphe) qui renvoie True si le graphe non oriente est biparti, False sinon.
Representation : le graphe est represente par un dictionnaire d'adjacence {sommet: [voisins]}.
Rappel : un graphe est biparti si on peut partitionner ses sommets en deux ensembles U et V tels que chaque arete relie un sommet de U a un sommet de V. De maniere equivalente (theoreme de Konig), un graphe est biparti si et seulement s'il ne contient pas de cycle de longueur impaire. On peut le verifier en tentant une 2-coloration par BFS.
Attention : le graphe n'est pas necessairement connexe.
| Appel | Résultat attendu |
|---|---|
| est_biparti({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}) | True |
| est_biparti({0: [1, 2], 1: [0, 2], 2: [0, 1]}) | False |
Connectez-vous pour soumettre du code.