informatique (tronc commun des prépas scientifiques) · Chapitre 12 · Exercice de TD
Symétriser et vérifier qu'un graphe est non orienté
Les graphes : modèle et représentations · niveau 2
É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 H