informatique (tronc commun des prépas scientifiques) · Chapitre 13 · Exercice de TD
Le graphe est-il un arbre ?
Parcours de graphes · niveau 2
É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) - 1Exercices semblables
- Mesurer le piège de la file-liste corrigé
- Sortir du labyrinthe corrigé
- Le graphe biparti, ou le coloriage en deux couleurs corrigé
- L'échelle des mots corrigé
- Les arbres, preuve du théorème corrigé