Skip to main content Informatique en prépa - Lycée Malherbe 

CCINP TSI 2024 - Colorer un graphe

Le sujet

Épreuve d'informatique de la filière TSI du Concours Commun INP, session 2024. Sujet original (PDF), © Concours Commun INP.

L'énoncé est reproduit tel quel (on répond ici dans les cellules et les tableaux plutôt que sur le Document Réponse, dont les canevas de code sont repris). Les cellules de code, les vérifications et la base de données ont été ajoutés pour le traiter sur machine : la base de données est fictive (et simplifiée).

Colorer un graphe

La coloration d'une carte de pays consiste à attribuer une couleur à chacun des pays de manière à ce que deux pays voisins soient de couleurs différentes.

Étudier ces techniques de coloration revient de façon plus abstraite à travailler sur des graphes. Le champ d'applications de la coloration de graphes est très vaste et couvre des domaines aussi variés que le problème de l'attribution de fréquences dans les télécommunications, la conception de puces électroniques ou l'allocation de registres en compilation.

Soulignons que tous les graphes considérés dans ce sujet sont non-orientés.

Partie I - Des algorithmes pour colorer un graphe

I.1 - Introduction sur un exemple

On cherche à colorer une carte de pays avec comme seule contrainte que deux pays ayant une frontière commune ne peuvent être de la même couleur.

Comme les pays, les couleurs sont numérotées à partir de zéro.

À titre d'exemple, on considèrera une carte comportant 8 pays numérotés de 0 à 7 (figure 1 du sujet : le pays 7 entoure les pays 0 à 4 ; le pays 0 entoure les pays 1, 2 et 3 ; les pays 4, 5 et 6 sont côte à côte), que l'on représentera par le graphe donné en figure 2 :

1 1 0 0 1--0 2 2 1--2 3 3 1--3 6 6 0--6 7 7 0--7 0--3 4 4 0--4 6--7 5 5 6--5 2--3 7--5 3--4 4--6 4--7 4--5

Figure 2 - Graphe Gex associé à la carte de pays de la figure 1

Ainsi, sur le graphe de la figure 2, deux pays sont voisins si et seulement si les sommets correspondants sont reliés par une arête.

Q1

Un graphe peut être représenté par une matrice d'adjacence. La matrice d'adjacence pré-remplie du graphe est donnée ci-dessous. La compléter et expliquer le processus de construction.

01234567
01011
10000
20000
31000
410010111
500001011
610001101
710001110
Réponse
Q2

Une autre manière de représenter en mémoire un graphe est d'utiliser une liste d'adjacence. La liste d'adjacence d'un graphe (constitué de sommets numérotés de 0 à ) est une liste LA, telle que LA[i] est la liste des sommets voisins du sommet i. Par convention, les voisins énumérés dans LA[i] seront listés dans l'ordre croissant.

Donner la liste d'adjacence du graphe présenté en exemple (dans la variable LA).

Python

Loading editor...

LA = 
Vérification : LA
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q3

Donner un avantage et un inconvénient d'une représentation par matrice d'adjacence.

Donner un avantage et un inconvénient d'une représentation par liste d'adjacence.

Réponse
Q4

On rappelle que le degré d'un sommet d'un graphe est le nombre de voisins du sommet , c'est-à-dire le nombre de sommets reliés à .

Compléter le tableau des degrés des différents sommets du graphe .

01234567
Degré

I.2 - Tester si une coloration est valide

Q5

Écrire une fonction voisins avec trois arguments, deux nombres entiers distincts i et j et une liste d'adjacence LA représentant un graphe, qui renvoie True si les sommets numérotés i et j sont reliés par une arête et False sinon.

Python

Loading editor...

def voisins(i, j, LA):
    pass
Vérification : voisins
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

On considère une carte de pays, représentée par un graphe pour laquelle on a une proposition de coloration donnée par une liste C. Ainsi, C[i] donne le numéro de la couleur attribuée au sommet i. On souhaite déterminer si la coloration proposée est valide (deux sommets du graphe reliés par une arête ne peuvent pas être de la même couleur).

Q6

Écrire la fonction coloration_valide avec pour arguments une liste d'adjacence LA et une liste de couleurs C, qui renvoie True si la coloration est valide, False sinon.

Python

Loading editor...

def coloration_valide(LA, C):
    pass
Vérification : coloration_valide
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q7

Pour un graphe comportant sommets, quelle est la complexité temporelle dans le pire des cas de la fonction coloration_valide ?

Réponse

I.3 - Un algorithme intuitif de coloration

L'attribution des couleurs à chaque sommet est caractérisée par une liste C où C[i] est la couleur attribuée au sommet i ; C[i] vaut −1 si la couleur n'est pas encore attribuée. La liste C ne contient que des −1 au départ et ses valeurs sont modifiées progressivement au fur et à mesure que les couleurs sont attribuées.

Q8

On suppose (dans cette question seulement) que n est une constante déjà définie. Écrire la ou les instruction(s) permettant de créer une liste initiale C composée de n éléments valant −1.

Python

Loading editor...

n = 8
Q9

Compléter la fonction colore_sommet ayant trois arguments, la liste C des couleurs attribuées, le numéro s du sommet à colorer et la liste d'adjacence LA caractérisant le graphe.

Cette fonction ne renvoie rien mais modifie la liste C en donnant à C[s] la plus petite couleur possible, en fonction des couleurs des sommets voisins qui sont déjà colorés.

Par exemple, pour le graphe , prenons C=[0,1,-1,-1,-1,-1,-1,-1]. Les sommets 0 et 1 ont donc déjà été colorés avec les couleurs C[0]=0 et C[1]=1.

L'appel colore_sommet(C,2,LA) modifie la liste C en C=[0,1,0,-1,-1,-1,-1,-1]. Cela veut dire que le sommet 2, adjacent au sommet 1 mais pas au sommet 0, a reçu la même couleur que le sommet 0.

Python

Loading editor...

def colore_sommet(C, s, LA):
    # on détermine la liste des couleurs des voisins de s déjà colorés
    coul_vois = []

    # coul_vois est maintenant déterminée et on recherche la
    # plus petite couleur, notée num_coul, absente de coul_vois :

    # la valeur num_coul trouvée devient la couleur du sommet s :
Vérification : colore_sommet
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q10

À l'aide de Q9, écrire une fonction colorer1 avec pour argument une liste LA caractérisant un graphe, qui crée et renvoie la liste C des numéros des couleurs attribuées en colorant les sommets un par un par ordre croissant de leurs numéros.

Par exemple, l'application de la fonction colorer1 au graphe renverra la liste de couleurs [0,1,0,2,1,0,2,3].

Python

Loading editor...

def colorer1(LA):
    pass
Vérification : colorer1
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q11

L'ordre de coloration imposé à la question précédente est arbitraire. On souhaite maintenant colorer le graphe en traitant les sommets selon un ordre arbitraire donné en argument.

Écrire une fonction colorer2 analogue à colorer1 et avec un argument supplémentaire, une liste ordre fixant l'ordre de coloration des pays.

Par exemple colorer2([0,2,4,6,1,3,5,7],LA) colorera le graphe en commençant d'abord par le sommet 0, puis en continuant par les sommets 2,4,6...

Python

Loading editor...

def colorer2(ordre, LA):
    pass
Vérification : colorer2
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q12

Donner la liste des couleurs renvoyée par colorer2 pour colorer le graphe donné en exemple en prenant ordre=[7,6,5,4,3,2,1,0].

Combien de couleurs ont-elles été utilisées ?

Python

Loading editor...

Réponse

La méthode que nous venons de décrire est rapide et fonctionne plutôt bien. Cependant, si on cherche à utiliser le nombre minimum de couleurs, l'efficacité de l'algorithme proposé ci-dessus dépend en grande partie de l'ordre dans lequel on choisit de colorer les sommets du graphe.

L'objectif des sous-parties suivantes est d'affiner la stratégie pour mieux choisir cet ordre de coloration.

I.4 - Variante de Welsh-Powell

Une alternative est donnée par la variante de Welsh-Powell. L'idée est de parcourir l'ensemble des sommets du graphe par ordre décroissant de leurs degrés.

Comme le degré d'un sommet est un entier positif, il est possible d'écrire un algorithme de tri efficace (dit par répartition).

Q13

Écrire une fonction degre avec pour argument la liste d'adjacence LA d'un graphe quelconque, qui renvoie la liste des degrés des sommets du graphe.

Par exemple, pour un graphe de liste d'adjacence LA=[[1,2],[0,2,3],[0,1,3],[1,2,4],[3]], la fonction degre renverra la liste [2,3,3,3,1].

Python

Loading editor...

def degre(LA):
    pass
Vérification : degre
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q14

Écrire une fonction init avec pour argument un entier n, qui renvoie une liste de listes R de taille n, telle que R[i] soit une liste vide.

Par exemple, init(3) renverra [[],[],[]].

Python

Loading editor...

def init(n):
    pass
Vérification : init
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q15

Écrire une fonction ranger avec pour argument une liste d'adjacence LA, qui renvoie une liste R de même taille que LA, telle que R[i] soit la liste des sommets de degré i.

Ainsi, pour l'exemple de la question Q13, l'appel ranger(LA) renverra la liste [[],[4],[0],[1,2,3],[]].

Python

Loading editor...

def ranger(LA):
    pass
Vérification : ranger
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q16

Écrire une fonction renverse avec pour argument une liste L, qui crée et renvoie une nouvelle liste obtenue en lisant L dans l'ordre inverse.

Par exemple, renverse([1,2,3,4]) renverra [4,3,2,1].

Python

Loading editor...

def renverse(L):
    pass
Vérification : renverse
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q17

Écrire une fonction trier_sommets avec pour argument une liste d'adjacence LA, qui renvoie la liste des sommets triés dans l'ordre décroissant de leur degré.

Par exemple, pour un graphe de liste d'adjacence LA=[[1,2],[0,2,3],[0,1,3],[1,2,4],[3]], la fonction trier_sommets renverra la liste de sommets [1,2,3,0,4].

Python

Loading editor...

def trier_sommets(LA):
    pass
Vérification : trier_sommets
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q18

Pour un graphe à sommets, quelle est la complexité temporelle de la fonction trier_sommets dans le pire des cas ?

Réponse
Q19

Écrire la fonction colorer3 avec pour argument une liste d'adjacence LA, qui crée et renvoie une liste de couleurs C, telle que C[i] soit la couleur à attribuer au sommet numéro i, les sommets étant colorés dans l'ordre décroissant de leur degré.

Quelle est la complexité de colorer3 dans le pire des cas pour un graphe à sommets ?

Python

Loading editor...

def colorer3(LA):
    pass
Vérification : colorer3
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Réponse
Q20

Pour le graphe de la figure 2, donner la liste C des couleurs renvoyée par la fonction colorer3.

Python

Loading editor...

Réponse

L'amélioration proposée donne de bons résultats dans un grand nombre de cas. Cependant, il reste quelques cas où la coloration obtenue utilise trop de couleurs.

La méthode suivante, proposée en 1979 par Daniel Brélaz de l'École Polytechnique Fédérale de Lausanne, raffine la détermination de l'ordre de coloration. La priorité de coloration est ainsi recalculée après chaque traitement d'un sommet et non plus une fois pour toute au départ. Au final, cette approche fournit rapidement une coloration optimale dans un très grand nombre de cas.

I.5 - Algorithme DSATUR

Lorsque l'on colore un graphe, le degré de saturation d'un sommet est le nombre de couleurs différentes déjà attribuées à ses différents sommets voisins. Évidemment, ce degré de saturation est susceptible d'évoluer à chaque fois qu'un nouveau sommet est coloré.

Q21

Écrire une fonction degre_satur avec 3 arguments, une liste d'adjacence LA, un sommet s du graphe, une liste C de couleurs. Cette fonction renvoie le degré de saturation du sommet s.

On rappelle que le sommet i est coloré si et seulement si C[i] est différent de −1.

Python

Loading editor...

def degre_satur(LA, s, C):
    pass
Vérification : degre_satur
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q22

Écrire une fonction liste_satur avec deux arguments, une liste d'adjacence LA, la liste C des couleurs des sommets, qui renvoie la liste des sommets non colorés du graphe ayant un degré de saturation maximum parmi les sommets non colorés.

On notera qu'il s'agit d'une liste car plusieurs sommets peuvent avoir le même degré de saturation. On supposera de plus qu'il reste au moins un sommet non coloré.

Python

Loading editor...

def liste_satur(LA, C):
    pass
Vérification : liste_satur
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q23

Écrire une fonction pas_fini avec pour argument une liste C, qui renvoie True si cette liste contient la valeur -1, False sinon.

Python

Loading editor...

def pas_fini(C):
    pass
Vérification : pas_fini
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q24

Compléter la fonction colorer4 ayant pour argument une liste d'adjacence LA, qui renvoie une liste C constituant une coloration du graphe. Cette fonction procède de la façon suivante.

Tant qu'il reste un sommet non coloré :

  • déterminer parmi les sommets non colorés ceux de degré de saturation maximale ;
  • si plusieurs sommets non colorés ont un degré de saturation maximale, en choisir un parmi ceux-ci qui soit de degré maximal ;
  • colorer le sommet choisi en lui attribuant la couleur disponible ayant la plus petite valeur.
Python

Loading editor...

def colorer4(LA):
    n =            # nombre de sommets du graphe
    D =            # liste des degrés des sommets du graphe
    C =            # initialisation de la liste des couleurs
    while            :
        # liste des sommets non colorés de degré de saturation maximal
        Ls =
        # en cas d'égalité, recherche du sommet de degré maximal

        # coloration du sommet prioritaire

    return C
Vérification : colorer4
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

Il n'est pas facile d'être certain d'avoir utilisé le nombre minimum de couleurs. La sous-partie suivante propose une piste.

I.6 - Un minorant du nombre de couleurs nécessaires

Considérons un graphe et un sous-ensemble de sommets de ce graphe. On dit que forme une clique si et seulement si pour chaque paire de sommets de , il existe une arête les reliant.

Par exemple, sur le graphe de la figure 2, (4, 5, 6, 7) constitue une clique de 4 sommets et (4, 5, 6) une clique de 3 sommets. Par contre, (0, 4, 5, 6, 7) ne forme pas une clique puisque le sommet 0 n'est pas relié au sommet 5.

Enfin, on note le cardinal de la plus grande clique de .

Q25

Justifier que le nombre minimum de couleurs pour colorer un graphe est supérieur ou égal au nombre .

Montrer également que : où désigne le degré du sommet dans le graphe .

Réponse

Dans ce qui suit, on suppose toujours que les sommets d'un graphe à sommets sont numérotés de 0 à .

Q26

Écrire une fonction est_clique avec deux arguments, la liste d'adjacence LA d'un graphe et un tuple K de sommets de ce graphe, qui renvoie True si K est une clique, False sinon.

Python

Loading editor...

def est_clique(LA, K):
    pass
Vérification : est_clique
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).
Q27

La fonction combinations du module itertools fournit toutes les combinaisons de taille fixée d'une liste :

>>> from itertools import combinations
>>> for C in combinations([0,1,2,3,4],3):
        print(C)
(0, 1, 2)
(0, 1, 3)
...
(2, 3, 4)

Compléter la fonction minoration_nb_couleurs ayant pour argument la liste d'adjacence LA d'un graphe, qui renvoie le cardinal de la plus grande clique du graphe considéré.

Python

Loading editor...

from itertools import combinations

def minoration_nb_couleurs(LA):
    n =                          # nombre de sommets du graphe
    S = [ k for k in range(n) ]  # liste des sommets du graphe
    i =
    test = True
    while test:
        for K in combinations(S,i):

        i=i-1
    return
Vérification : minoration_nb_couleurs
Teste les fonctions que vous avez écrites (exécutez d'abord les blocs où elles sont définies).

Ainsi, si le nombre de couleurs utilisées pour colorer le graphe est égal à , on est sûr d'avoir utilisé le nombre minimum de couleurs.

Partie II - Interrogation d'une base de données géographiques

On dispose d'une base de données composée de quatre tables :

On a toujours code_pays1<code_pays2 pour l'ordre lexicographique, ce qui assure que chaque frontière n'apparaît qu'une fois dans la table Frontieres.

Annexe 1 : extrait de la base de données

| nom | surface | | --- | --- | | 'Asie' | 44579000 | | 'Europe' | 9938000 | | ... | ... |

nomcode_payscapitalepopulation
'Albanie''AL''Tirana'3088385
'Algerie''DZ''Alger'44487616
............
code_payscontinent
'AL''Europe'
'DZ''Afrique'
......
code_pays1code_pays2longueur
'AL''GR'282.8
'AL''MK'151.5
.........
Q28

Écrire une requête SQL permettant de récupérer le code du pays nommé 'France'.

SQL

Loading editor...

Q29

Écrire une requête SQL permettant d'obtenir les noms des pays appartenant au continent 'Europe'.

SQL

Loading editor...

Dans les deux dernières questions, on admet que le code du pays nommé 'France' est 'F' et on peut utiliser librement cette information.

Q30

Écrire une requête SQL permettant de récupérer la longueur totale de la frontière du pays nommé 'France'.

SQL

Loading editor...

Q31

Écrire une requête SQL permettant de récupérer les noms des pays frontaliers du pays nommé 'France'.

SQL

Loading editor...


Entrez le code donné en cours pour accéder à la solution :