Graphes & applications

Correction de la série 1 : Coloration

Année Universitaire : 2024-2025

1 / 29
 Énoncé de l’exercice 1

On désire attribuer des canaux de fréquences-radio à six stations. Deux

stations distantes de moins de 180 km ne peuvent pas utiliser le même
canal. Le tableau suivant décrit les distances qui séparent les différentes
stations.

- A B C D E F
A - 85 175 200 50 100
B 85 - 125 175 100 160
C 175 125 - 100 200 250
D 200 175 100 - 210 130
E 50 100 200 210 - 100
F 100 160 250 130 100 -

2 / 29
 Énoncé de l’exercice 1

1. À quel problème en théorie des graphes, ce contexte se ramène-t-il ?

2. Donner le graphe décrivant les incompatibilités liées à l’affectation des
fréquences.
3. Déterminer une affectation optimale.

3 / 29
 Correction exercice 1

1. Comme il faudrait attribuer le moins de canaux de fréquence-radios à six

stations (qui ne peuvent pas forcément utiliser le même canal), il s’agit
donc d’un problème de coloration.

2. On désigne par le graphe G le graphe décrivant les incompatibilités liées

à l’affectation des fréquences où

▶ Les sommets représentent les stations.

▶ Les arêtes représentent l’incompatibilité (distance entre deux stations
inférieure à 180 km ).
▶ Une couleur représente un canal.

4 / 29
 Correction exercice 1
- A B C D E F
A - 85 175 200 50 100
B 85 - 125 175 100 160
C 175 125 - 100 200 250
D 200 175 100 - 210 130
E 50 100 200 210 - 100
F 100 160 250 130 100 -

5 / 29
 Correction exercice 1
- A B C D E F
A - 85 175 200 50 100
B 85 - 125 175 100 160
C 175 125 - 100 200 250
D 200 175 100 - 210 130
E 50 100 200 210 - 100
F 100 160 250 130 100 -

6 / 29
 Correction exercice 1

3. Nous appliquons l’algorithme de Welch & Powell :

Pour cela, nous calculons les degrés des sommets du graphe. Puis, nous les
plaçons dans un ordre décroissant par rapport à leur degré.

Sommets B A F C D E
Degrés 5 4 4 3 3 3
Itération 1 C1 - - - - -
Itération 2 X C2 - - C2 -
Itération 3 X X C3 C3 X -
Itération 4 X X X X X C4

7 / 29
 Correction de l’exercice 1

Comme nous avons trouvé une coloration possible de 4 couleurs, donc

χ(G ) ≤ 4. Or, G contient un sous-graphe complet d’ordre 4 (formé par les
sommets A,B,E et F). Ainsi 4 ≤ χ(G ) ≤ 4 et donc, χ(G ) = 4.

Donc l’affectation optimale est :

▶ Canal 1 : la station B
▶ Canal 2 : les stations A et D
▶ Canal 3 : les stations F et C
▶ Canal 4 : la station E

8 / 29
 Énoncé de l’exercice 2

Dans une entreprise, six projets sont à réaliser. Quatre ingénieurs

multidisciplinaires sont disponibles : l1 , l2 , l3 et l4 . Chaque projet nécessite
deux ingénieurs, comme indiqué dans le tableau ci-dessous.
Plan
Projet Ingénieurs
1 I1 et I2
2 I1 et I3
3 I3 et I4
4 I2 et I4
5 I3 et I4
6 I1 et I3

9 / 29
 Énoncé de l’exercice 2

Deux projets peuvent s’éxécuter au même temps que s’ils impliquent deux
équipes différentes (à 100%).
1. Certains projets ne peuvent pas être réalisés en même temps.
Représenter ces contraintes par un graphe.
2. On suppose que le temps nécessaire pour chaque travail est d’une
semaine. Déterminer le nombre minimal de séquences nécessaires pour
réaliser ces six projets.
3. Proposer une organisation.

10 / 29
 Correction de l’exercice 2
1. Représentation du problème par un graphe G :
▶ Les sommets représentent les projets.
▶ Les arêtes représentent l’incompatibilité (même ingénieur impliqué
dans les deux projets).
▶ Les couleurs représentent les séquences.

11 / 29
 Correction de l’exercice 2
Plan
Projet Ingénieurs
1 I1 et I2
2 I1 et I3
3 I3 et I4
4 I2 et I4
5 I3 et I4
6 I1 et I3

12 / 29
 Correction de l’exercice 2
Plan
Projet Ingénieurs
1 I1 et I2
2 I1 et I3
3 I3 et I4
4 I2 et I4
5 I3 et I4
6 I1 et I3

13 / 29
 Correction de la série 2

2.

Application de Welch & Powell

Sommets 2 3 5 6 1 4
Degrés 4 4 4 4 3 3
Itération 1 C1 - - - - C1
Itération 2 X C2 - - C2 X
Itération 3 X X C3 - X X
Itération 4 X X X C4 X X

D’après la coloration ci-dessus, χ(G ) ≤ 4. Mais comme le graphe contient

un sous-graphe complet d’ordre 4 (formé par les sommets 2,3,5 et 6), dans
ce cas là χ(G ) = 4.

14 / 29
 Correction de l’exercice 2

3. Il faut au moins 4 séquences pour réaliser les 6 projets :

▶ Séquence 1 : projets 2 et 4.
▶ Séquence 2 : projets 3 et 1.
▶ Séquence 3 : projet 5.
▶ Séquence 4 : projet 6.

15 / 29
 Énoncé de l’exercice 3

Un groupe de 7 jeunes scouts venus des quatre régions décident d’explorer

la forêt. Le Scouter (Scout leader) souhaite repartir les jeunes scouts en
groupes de telle sorte que chaque groupe ne devrait pas inclure des scouts
de la même région ou des scouts dont la différence d’âge est supérieure ou
égal à 3 ans. Un groupe composé d’un seul membre sera accepté. Le
tableau ci-dessous résume les détails des 7 jeunes scouts.
Région Nom du scout Age (ans)
Région 1 Mohamed 14
Région 1 Farid 16
Région 2 Imed 13
Région 2 Imen 13
Région 3 Karim 17
Région 3 Zeinab 13
Région 4 Mourad 16

16 / 29
 Énoncé de l’exercice 3

1. À quel problème de théorie des graphes, ce contexte se ramène-t-il ?

2. Combien de groupes au minimum faudrait-il pour réaliser ce souhait ?
Expliquer votre démarche et préciser les étapes intermédiaires de votre
résolution.

17 / 29
 Correction de la série 3

1. Pour pouvoir répartir les scouts dans des groupes en prenant en compte
les incompatibilités entre-eux, on se ramène à résoudre un problème de
coloration.

18 / 29
 Correction de la série 3
Région Nom du scout Age (ans)
Région 1 Mohamed 14
Région 1 Farid 16
Région 2 Imed 13
Région 2 Imen 13
Région 3 Karim 17
Région 3 Zeinab 13
Région 4 Mourad 16

19 / 29
 Correction de la série 3
Région Nom du scout Age (ans)
Région 1 Mohamed 14
Région 1 Farid 16
Région 2 Imed 13
Région 2 Imen 13
Région 3 Karim 17
Région 3 Zeinab 13
Région 4 Mourad 16

20 / 29
 Correction de l’exercice 3
2.
Appliquons l’algorithme de Welch & Powell

Sommets Farid Imen Karim Imed Zeineb Mourad Mohamed

Degrés 4 4 4 4 3 3 2
Itération 1 C1 - C1 - - C1 -
Itération 2 X C2 X - C2 X C2
Itération 3 X X X C3 X X X

D’après la coloration ci-dessus, une répartition possible des scouts est en 3

groupes, c-à-d, χ(G ) ≤ 3.
Maintenant, comme le graphe représentant les contraintes contient un
sous-graphe complet d’ordre 3 (formé par Imed, Imen et Karim), on conclut
que le nombre de couleurs/groupes minimal est 3, c-à-d, χ(G ) = 3.

▶ Groupe 1 : Farid, Karim et Mourad.

▶ Groupe 2 : Imen, Zeineb et Mohamed.
▶ Groupe 3 : Imed.
21 / 29
 Énoncé de l’exercice 4

Treize rencontres opposeront sept équipes de foot A, . . . , G . Les rencontres

prévues sont décrites dans le tableau suivant :

A × × − − − ×
B × × − × −
C × × − −
D × × −
E × ×
F ×
G
Chacune des équipes ne pourra jouer qu’un seul match par semaine.
1. Représenter les contraintes de ce problème par un graphe (indication :
les sommets représentent les rencontres : AB, AC , . . . ).
2. Déterminer le nombre minimum de semaines nécessaires pour planifier
l’ensemble des rencontres.

22 / 29
 Correction exercice 4
1. Le graphe qui représente les contraintes :
▶ Les sommets représentent les rencontres.
▶ Les arêtes représentent l’incompatibilité (une même équipe joue dans
les deux rencontres).
▶ Les couleurs représentent les semaines où se passent les rencontres.

23 / 29
 Correction exercice 4
1. Le graphe qui représente les contraintes :
▶ Les sommets représentent les rencontres.
▶ Les arêtes représentent l’incompatibilité (une même équipe joue dans
les deux rencontres).
▶ Les couleurs représentent les semaines où se passent les rencontres.

24 / 29
 Correction de l’exercice 4

2. Un nombre de semaines possible pour planifier l’ensemble des rencontres

est de 5 semaines. En effet, par l’algorithme de Welch & Powell :

Sommets BC BF CE DF BD CD DE EF AB AC EG FG AG
Degrés 6 6 6 6 6 6 6 6 5 5 5 5 4
Itération 1 C1 - - C1 - - - - - - C1 - -
Itération 2 X C2 C2 X - - - - - - X - C2
Itération 3 X X X X C3 - - C3 - C3 X - X
Itération 4 X X X X X C4 - X C4 X X C4 X
Itération 5 X X X X X X C5 X X X X X X

25 / 29
 Énoncé de l’exercice 5

L’objectif de ce problème est de déterminer une planification de passage de

voitures à travers un rond-point, en respectant des contraintes
d’incompatibilité. Le graphe suivant décrit le croisement étudié ainsi que
les itinéraires (Li) possibles.

Donner une planification des feux au niveau de ce croisement en tenant

compte des incompatibilités des itinéraires.

26 / 29
 Correction de l’exercice 5
Le graphe qui représente les contraintes :
▶ Les sommets représentent les itinéraires.
▶ Les arêtes représentent l’incompatibilité (les deux itinéraires se
chevauchent en partie).
▶ Les couleurs représentent les séquences de feux.

27 / 29
 Correction de l’exercice 5
Le graphe qui représente les contraintes :
▶ Les sommets représentent les itinéraires.
▶ Les arêtes représentent l’incompatibilité (les deux itinéraires se
chevauchent en partie).
▶ Les couleurs représentent les séquences de feux.

28 / 29
 Correction de l’exercice 5

Appliquons l’algorithme de Welch & Powell

Sommets L2 L4 L6 L8 L1 L9 L3 L5 L7
Degrés 5 5 5 5 4 4 2 2 2
Itération 1 C1 - - - C1 - C1 - -
Itération 2 x C2 - - x C2 x C2 -
Itération 3 x x C3 - x x x x C3
Itération 4 x x x C4 x x x x x

Une planification des feux pour organiser ce carrefour est, donc, possible en
4 séquences. De plus, elle est minimale grâce à l’existence d’un sous-graphe
complet d’ordre 4 (formé par L2 , L4 , L6 et L8 ).
▶ Séquence 1 : L2 , L1 et L3 .
▶ Séquence 2 : L4 , L9 et L5 .
▶ Séquence 3 : L6 et L7 .
▶ Séquence 4 : L8 .

29 / 29