Exercice 3 - Graphes · Bac Numérique et Sciences Informatiques Amérique du Nord 2025 (jour 1)

Partie B: graphes et algorithmique

Afin de faciliter en amont les préparations des sorties, on souhaite construire le graphe non orienté des mésententes entre les enfants de l'association. Le graphe est représenté par un dictionnaire dont les clés sont les sommets du graphe, et qui associe à chaque sommet le tableau (type List en Python) de ses voisins.

Par exemple, le graphe g1 de la figure 2 est représenté par le dictionnaire suivant:

g1 = {'Elise': ['Octavie', 'Virgile'],

'Octavie': ['Elise', 'Pierre', 'Virgile'],

'Pierre': ['Octavie', 'Raphael'],

'Raphael': ['Pierre', 'Virgile'],

'Sixtine': [],

'Virgile': ['Elise', 'Octavie', 'Raphael']

}

10.

Expliquer pourquoi la situation décrite ne nécessite qu'un graphe non orienté.

11.

Dessiner le graphe g2 défini ci-dessous:

g2 = {'Adrien': ['Elisabeth', 'Lea'],

'Elisabeth': ['Adrien', 'Ian', 'Luca'],

'Ian': ['Elisabeth', 'Joseph', 'Luca'],

'Joseph': ['Ian'],

'Lea': ['Adrien'],

'Luca': ['Elisabeth', 'Ian']

}

12.

Écrire une fonction degre, qui prend en arguments un dictionnaire g représentant un graphe et une chaîne de caractères s représentant un sommet du graphe, et qui renvoie le degré du sommet s dans g. On rappelle que le degré d'un sommet est le nombre d'arêtes issues de ce sommet.

Pour faire des groupes de personnes qui peuvent s'entendre, une méthode consiste à colorer le graphe, c'est-à-dire attribuer une couleur à chacun de ses sommets, en prenant garde qu'aucune arête ne relie deux sommets de même couleur. Ainsi les sommets d'une même couleur forment un groupe de personnes qui peuvent s'entendre. Par la suite, les couleurs sont représentées par des nombres entiers positifs, et -1 représente l'absence de couleur.

En notant les couleurs par différents nombres précisés sous les sommets, le graphe g1 ci-dessus est associé au dictionnaire des couleurs dc1 suivant:

dc1 = {'Elise': 0, 'Octavie': 1, 'Pierre': 2, 'Raphael': 3, 'Sixtine': 4, 'Virgile': 5}

On peut utiliser moins de couleurs dans cet exemple.

15.

Recopier et colorer le graphe g1 en n'utilisant que trois couleurs (0, 1 et 2).

Une méthode simple pour colorer le graphe consiste à parcourir les sommets et numéroter (colorer) chaque sommet s par le plus petit numéro non utilisé par ses voisins. On dispose de la fonction plus_petite_couleur_hors_voisins(g, dc, s) définie ainsi:

def couleurs_voisins(g, dc, s):

return [dc[v] for v in g[s]]

def plus_petite_couleur_hors_voisins(g, dc, s):

couleur = 0

n = len(g)

cvoisins = couleurs_voisins(g, dc, s)

while couleur < n:

if couleur not in cvoisins:

return couleur

couleur = couleur + 1

return couleur

16.

Recopier et compléter la procédure colorer_graphe qui permet de colorer le graphe en modifiant le dictionnaire dc pour qu'il associe finalement à chaque sommet de g sa couleur:

def colorer_graphe(g, dc):

# Pré-condition: les clés de dc sont les sommets

# de g, et les valeurs de dc sont toutes à -1

for s in dc:

couleur =...

... = couleur

17.

L'algorithme de Welsh-Powell consiste à colorer le graphe dans l'ordre des sommets par degré décroissant. Recopier et compléter le code de la fonction welsh_powell donné ci-après. Cette fonction prend en paramètre un dictionnaire g et renvoie le dictionnaire des couleurs associé. On pourra utiliser la fonction sommets_tries:

def welsh_powell(g):

# initialisation à -1 pour tous les sommets dans le dictionnaire dc

dc =...

# coloration en suivant l'approche de Welsh-Powell

for...

...

...

return dc