Corrigé CCINP 2025 Maths 2 MP — Exercice 1 (Q1 à Q6) : Graphes orientés en dictionnaire d'adjacence, coloration ; SQL : agrégats et HAVING

Q1. Dans un dictionnaire d'adjacence, le degré sortant du sommet s est la longueur de la liste de ses successeurs, len(d[s]). On calcule le maximum de ces longueurs par un parcours des clés, en partant de $0$ (un degré est toujours positif ou nul) :

def degreMax(d: dict) -> int:
    m = 0
    for s in d:
        if len(d[s]) > m:
            m = len(d[s])
    return m

Après le traitement des clés déjà vues, m est le plus grand de leurs degrés sortants (invariant de boucle, vrai au départ pour l'ensemble vide avec la valeur $0$) ; à la sortie, c'est donc le degré sortant maximal du graphe. Sur l'exemple, les degrés sortants des sommets $0$ à $6$ sont $2,1,2,1,1,0,1$ et la fonction renvoie $2$. Pour un graphe sans sommet, elle renvoie $0$.

Ce que le correcteur attend : le rapport du jury rappelle que la fonction max() de Python ne doit pas être utilisée : on écrit la boucle. Il signale aussi la confusion fréquente entre clés et valeurs du dictionnaire : for s in d parcourt les clés (les sommets), et d[s] est la valeur associée (la liste des successeurs).

Q2. Le graphe inverse de l'exemple. Les arcs du graphe d'exemple sont $0\to 1$, $0\to 3$, $1\to 2$, $2\to 4$, $2\to 5$, $3\to 4$, $4\to 1$, $6\to 2$ ; on les retourne : $1\to 0$, $3\to 0$, $2\to 1$, $4\to 2$, $5\to 2$, $4\to 3$, $1\to 4$, $2\to 6$.

Son dictionnaire d'adjacence est \{0:[], 1:[0,4], 2:[1,6], 3:[0], 4:[2,3], 5:[2], 6:[]\}.