Théorie des graphes
Série 1 (Correction): Coloriage
des sommets d’un graphe
[email protected]
December 7, 2020
Exercice 1.
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.
|
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.
Correction exercice 1.
3
1. Il s’agit d’un problème de coloration. Il faudrait trouver une bonne
affectation des fréquences-radio.
2. On désigne par le graphe G = (V , E) le graphe décrivant les
incompatibilités liées à l’affectation des fréquences.
Avec, l’ensemble des sommets V réprésente les stations et
l’ensemble des arêtes E représente l’incompatibilités (distance ≤ 180
km) et une couleur représentation une affection possible (canal).
|
3. Application de l’algorithme de WELCH & POWELL
d(A) = 4, d(B) = 5, d(C) = 3, d(D) = 3, d(E) = 3, d(F ) = 4.
On a χ(G) ≤ 4, or G contient un K4 (représenté en bleu).
Ainsi 4 ≤ χ(G) ≤ 4 et donc, χ(G) = 4.
Donc l’affectation optimale est:
Exercice 2.
7
Dans une entreprise, six projets sont à réaliser. Quatre ingénieurs
multidisciplinaires sont disponibles: I1 , I2 , I3 et I4 . Chaque projet
nécessite deux ingénieurs, comme indiqué dans le tableau
ci-dessous.
|
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.
Correction exercice 2.
9
1. Représentation du problème par un graphe G = (V , E)
• Les sommets représentent les projets.
• Les arêtes représentent l’incompatibilités.
• Les couleurs représentent les séquences.
|
2. WELCH & POWELL
χ(G) = 4 (existence d’un K4 ).
3. 4 séquences sont nécessaires pour réaliser les 6
projets
Exercice 3.
13
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.
|
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.
Correction exercice 3.
15
1. Ce problème ramène à un problème de coloration pour gérer les
incompatibilités.
|
2. WELCH & POWELL
Il faudra exactement 3 groupes pour répartir les scouts selon les
contraintes souhaitées..
Exercice 4.
18
Treize rencontres opposeront sept Èquipes de foot A, . . . , G. Les
rencontres prévues sont décrites dans le tableau suivant:
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.
|
Correction exercice 4.
19
1. Le graphe qui représente les contraintes est la suivante:
|
2. le nombre minimum de semaines nécessaires pour planifier
l’ensemble des rencontres:
Exercice 5.
22
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.
|
Correction exercice 5.
23
|
L’algorithme de WELSH & POWELL
