Exercices de programmation pour classes préparatoires
Ecrire une fonction a_cycle(graphe) qui renvoie True si le graphe non oriente contient au moins un cycle, False sinon.
Representation : le graphe est represente par un dictionnaire d'adjacence {sommet: [voisins]}.
Rappel : un cycle dans un graphe non oriente est un chemin fermé de longueur au moins 3 qui ne passe pas deux fois par la meme arete. Un graphe connexe a n sommets et n-1 aretes est un arbre (sans cycle). Si le nombre d'aretes est superieur ou egal a n, il y a forcement un cycle.
| Appel | Résultat attendu |
|---|---|
| a_cycle({0: [1, 2], 1: [0], 2: [0]}) | False |
| a_cycle({0: [1, 2], 1: [0, 2], 2: [0, 1]}) | True |
Connectez-vous pour soumettre du code.