informatique (tronc commun des prépas scientifiques) · Chapitre 12 · Exercice de TD
Compter les triangles
Les graphes : modèle et représentations · niveau 2
Énoncé
Écrire la fonction nb_triangles(G) pour dénombrer les sous-graphes complets de 3 sommets mutuellement connectés dans un graphe non orienté sans doublon de comptage.
Corrigé
On impose un ordre arbitraire sur les sommets pour assurer l'unicité du parcours :
def nb_triangles(G: dict) -> int:
c = 0
for u in G:
for v in G[u]:
if v > u:
for w in G[v]:
if w > v and w in G[u]:
c += 1
return cLa complexité est de si les voisinages sont modélisés par des ensembles (ou si le test w in G[u] s'effectue sur un dictionnaire).