Le graphe est-il un arbre ?
Exercice · informatique (tronc commun des prépas scientifiques), chapitre 13 — Parcours de graphes
Énoncé
Écrire la fonction est_un_arbre(G) pour un graphe non orienté de deux manières.
Corrigé
# Approche A : Connexe et sans cycle
def est_un_arbre(G: dict) -> bool:
return est_connexe(G) and not a_un_cycle(G)
# Approche B : Connexe et possédant exactement n-1 arêtes
def est_un_arbre_compte(G: dict) -> bool:
nb_aretes = sum(len(G[s]) for s in G) // 2
return est_connexe(G) and nb_aretes == len(G) - 1Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.