Prépa Code Connexion Inscription

On représente un graphe non orienté par sa matrice d'adjacence : graphe[i][j] vaut 1 si les sommets i et j sont reliés par une arete, 0 sinon.

Écrire une fonction coloration(graphe, k) qui détermine s'il est possible de colorier les sommets du graphe avec au plus k couleurs, de sorte que deux sommets adjacents n'aient jamais la meme couleur. La fonction renvoie une liste donnant la couleur (un entier de 0 a k-1) de chaque sommet, ou une liste vide [] si c'est impossible.

Plusieurs colorations peuvent convenir : les tests vérifient seulement que la coloration renvoyée est valide (bonne longueur, couleurs entre 0 et k-1, deux voisins de couleurs différentes). N'importe quelle coloration correcte est acceptée.

On utilisera un algorithme de backtracking : pour chaque sommet, essayer les couleurs de 0 a k-1 ; vérifier que la couleur est compatible avec les voisins déja coloriés ; si oui, passer au sommet suivant ; sinon, revenir en arriere.