Symétriser et vérifier qu'un graphe est non orienté
Exercice · informatique (tronc commun des prépas scientifiques), chapitre 12 — Les graphes : modèle et représentations
Énoncé
Écrire est_symetrique(G) pour valider qu'un graphe en listes d'adjacence est non orienté, puis une fonction de correction symetrise(G).
Corrigé
def est_symetrique(G: dict) -> bool:
for u in G:
for v in G[u]:
if u not in G[v]:
return False
return True
def symetrise(G: dict) -> dict:
# Création d'une copie pour préserver le graphe d'origine (fonction pure)
H = {s: list(G[s]) for s in G}
for u in G:
for v in G[u]:
if u not in H[v]:
H[v].append(u)
return HLes 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.