Compter les triangles

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 12 — Les graphes : modèle et représentations

É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 $u < v < w$ 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 c

La complexité est de $O (m \cdot d_{m a x})$ si les voisinages sont modélisés par des ensembles (ou si le test w in G[u] s'effectue sur un dictionnaire).

Les 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.