Corrigé emlyon 2025 Maths appliquées ECG — Exercice 2 — Partie B (Q9 à Q12.b) : Coloration gloutonne d'un graphe en Python : voisins, plus petit entier absent, déroulé sur un graphe à six sommets, coloration à trois couleurs

Q9. Le sommet $s_j$ est voisin de $s_i$ lorsque $j\ne i$ et que le coefficient $a_{i,j}$ de la matrice d'adjacence vaut $1$ (arête entre $s_i$ et $s_j$). On ajoute alors à V le numéro j :

def voisins(A, i):
    n = len(A[i])
    V = []
    for j in range(n):
        if j != i and A[i, j] == 1:
            V.append(j)
    return V

len(A[i]) est la longueur de la ligne $i$, c'est-à-dire l'ordre $n$ du graphe. Le test j != i écarte une éventuelle boucle (un sommet n'est pas son propre voisin, par définition). Avec un tableau numpy, A[i, j] et A[i][j] désignent le même coefficient. La fonction renvoie la liste des numéros des voisins, par ordre croissant.

Q10. On transcrit l'algorithme proposé ; le test d'appartenance d'un élément à une liste s'écrit m in L :

def min_ext(L):
    m = 0
    while m in L:
        m = m + 1
    return m

Terminaison : la liste $L$ est finie, donc l'un des entiers $0,1,\dots ,\mathrm{len}(L)$ n'est pas dans $L$, et la boucle s'arrête au plus tard pour $m=\mathrm{len}(L)$. Correction : à la sortie, $m\notin L$, et tous les entiers $0,\dots ,m-1$ ont été trouvés dans $L$ ; $m$ est donc le plus petit entier naturel absent de $L$. Exécution : min_ext([1, 0, 3]) renvoie 2, comme dans l'exemple du sujet.

Ce que le correcteur attend : m in L (appartenance) et non m == L (qui compare un entier à une liste et vaut toujours False).