Mathématique m1419

L'optimisation à l'aide de graphes

Les graphes sont une façon utile de représenter certaines situations. À l'aide de ces graphes, il est possible d'optimiser ou de résoudre des situations qui, a première vue, peuvent nous apparaître très complexes. Voici quelques méthodes d'optimisation à l'aide des graphes.

Le chemin critique

Dans certains types de situation, il est possible de représenter les différentes étapes à l'aide d'un graphe valué et orienté. Ainsi, il sera visuellement possible de voir différents chemins partant tous du même point d'origine et se rendant au même point final. Certains de ces chemins peuvent être parallèles, ce qui signifie que les étapes qui les composent peuvent se dérouler en même temps. Parmi tous ces chemins, celui ayant le plus grand poids est le chemin critique. Le poids ici représente le temps minimal qu'il faut considérer pour réaliser le projet au complet.

Étapes de résolution d'un problème avec l'utilisation du chemin critique :

1. Représenter la situation à l'aide d'un graphe valué et orienté en tenant compte des étapes préalables.

2. Déterminer le poids de chacun des chemins qui relient le sommet du début et le sommet de la fin.

3. Le chemin critique du graphe correspond au chemin qui a le plus grand poids. Il suffit d'interpréter la réponse selon la situation.

 

Produire un album de finissant

Le comité des finissants d'une école secondaire se prépare à la production d'un album de finissants. La directrice de l'école leur demande d'estimer le temps requis pour la production de leur album. Voici un tableau qui présente les étapes à faire pour la réalisation de l'album de finissants.

Tâches Temps (jours) Préalables
A : Acheter les films1Aucun
B : Charger les caméras1A
C : Prendre les photos du conseil étudiant3A-B
D : Prendre les photos des enseignants2A-B
E : Prendre les photos des clubs sportifs1A-B
F : Faire développer les photos2C-D-E
G : Faire la mise en page5F
H : Faire signer par le comité de l’album3G
I : Faire signer par la directrice2G
J : Imprimer les albums5H-I

Déterminer le nombre minimum de jours requis pour la production de l'album de finissants.

Solution

Étape 1



Étape 2

Début - A - B - C - F - G - H - J - Fin = 20  
Début - A - B - C - F - G - I - J - Fin = 19
Début - A - B - D - F - G - H - J - Fin = 19
Début - A - B - D - F - G - I - J - Fin = 18
Début - A - B - E - F - F - H - J - Fin = 18
Début - A - B - E - F - G - I - J - Fin = 17

Étape 3

Dans cet exemple, le chemin critique est "Début - A - B - C - F - G - H - J - Fin" puisque son poids est le plus élevé, soit 20 jours. On peut donc affirmer que la production de l'album prendra au minimum 20 jours.

L'arbre de valeur minimale ou maximale

Dans le type de situation présentant, par exemple, des situations impliquant des réseaux, il est souvent demandé de minimiser ou de maximiser les coûts ou les distances. Il faut donc trouver l'arbre de la valeur minimale ou maximale qui relie entre eux tous les sommets d'un graphe.

Étapes de résolution d'un problème avec l'utilisation de l'arbre de valeur minimale:

1. Énumérer toutes les arêtes du graphe et les placer en ordre croissant de poids.

2. Sélectionner l'arête ayant le plus petit poids qui ne forme pas déjà un cycle avec les arêtes déjà sélectionnées jusqu'à ce que tous les sommets du graphe soient reliés.

3. S'il y a lieu, calculer le poids de l'arbre obtenu et interpréter la réponse selon la situation.

Étapes de résolution d'un problème avec l'utilisation de l'arbre de valeur maximale:

1.
Énumérer toutes les arêtes du graphe et les placer en ordre décroissant de poids.

2. Sélectionner l'arête ayant le plus grand poids qui ne forme pas déjà un cycle avec les arêtes déjà sélectionnées jusqu'à ce que tous les sommets du graphe soient reliés.

3. S'il y a lieu, calculer le poids de l'arbre obtenu et interpréter la réponse selon la situation.

 

Construction de trottoirs

Un entrepreneur doit relier 6 immeubles par des trottoirs de béton. Il soumet une première estimation du coût de l'opération, représenté par le graphe ci-dessous.



On veut minimiser le coût total de la construction de ces trottoirs en s'assurant que tous les immeubles soient reliés.

Solution

Étape 1

Placer les arêtes en ordre croissant de poids.
EF - CE - BE - BD - BF - BC - AB - AF - CF

Étape 2

On sélectionne les arêtes EF, EC, EB et DB, puisqu'elles ont les plus petits poids et ne font pas partie du cycle. Afin que tous les sommets soient reliés, on va sélectionner aussi l'arête AB. Voici le graphe résultant.



Étape 3

Le poids de l'arbre de valeurs minimales est donc de 4 545 (750+790+835+850+1320). Le coût minimal de la construction des trottoirs reliant tous les immeubles est 4 545$.

La chaîne de poids minimal

Dans certaines situations, il sera question de trouver la chaîne de poids minimal reliant deux points en particulier dans un graphe valué. Cette chaîne de poids minimal porte aussi le nom de chaîne optimale.

Étapes pour la recherche de la chaîne optimale entre deux sommets dans un graphe valué:

1.
Trouver la chaîne ayant la plus petite valeur reliant le sommet de départ à chacun des sommets qui lui sont adjacents, puis inscrire le poids de cette chaîne ainsi que le sommet de provenance entre parenthèses pour chaque sommet évalué.

2. Répéter la première étape pour chaque sommet adjacent à ceux évalués précédemment jusqu'au dernier sommet.

3. Procéder à rebours pour reconstituer la chaîne optimal en partant du dernier sommet jusqu'au sommet de départ.

  

Le chemin le plus court

Voici le plan d'un quartier regroupant 6 immeubles. On veut savoir quel est le chemin plus court qui relie l'immeuble A et l'immeuble F.
m1419i20b.png 
Solution

1.Trouver la chaîne ayant la plus petite valeur reliant le sommet de départ à chacun des sommets qui lui sont adjacents, puis inscrire le poids de cette chaîne et le sommet de provenance entre parenthèses pour chaque sommet évalué.

Le sommet A est le sommet de départ. Les sommets adjacents sont B, C et D. On recherche donc la chaîne ayant la plus petite valeur reliant chacun de ces sommets au sommet de départ.

Pour B, la chaîne ayant la plus petite valeur, 2, est celle provenant directement de A. On inscrit donc 2(A) juste à côté du sommet B.
Pour C, la chaîne provenant directement du sommet A a une valeur de 7, mais celle passant par le sommet B a une valeur plus petite, soit 2+4=6. On choisit donc cette dernière en inscrivant 6(B).
Pour D, la chaîne ayant la plus petite valeur est aussi celle provenant de B, avec une valeur de 2+4=6 également. On y inscrit 6(B).
m1419i21b.png 
2.Répéter la première étape pour chaque sommet adjacent à ceux évalués précédemment jusqu'au dernier sommet.

Comme nous avons évalués les sommets B, C et D, nous devons maintenant appliquer la même procédure aux sommets adjacents, soit E et F.

Pour E, la chaîne provenant de B a une valeur de 2+3=5, celle provenant de C a une valeur de 6+5=11 et celle issue de D, une valeur de 6+2=8. On choisit donc la chaîne issue du sommet B en inscrivant (5)B à côté de E.
Pour F, en procédant de la même façon, on trouve que la chaîne de poids minimal est celle provenant du sommet E, avec une valeur de 5+4=9. On y inscrit donc 9(E).
m1419i23c.png  
3. Procéder à rebours pour reconstituer la chaîne optimal en partant du dernier sommet jusqu'au sommet de départ.

En partant du dernier sommet F, on suit les indications que nous avons inscrit à côté de chaque sommet pour reconstituer la chaîne de poids minimal jusqu'au sommet de départ.
m1419i24b.png
La chaîne optimale recherchée est donc la chaîne A-B-E-F avec une valeur de 9.

Le nombre chromatique

Si une situation inclut une planification en tenant compte des incompatibilités entre certains des éléments impliqués, il peut s'avérer utile de recourir à un graphe coloré. Ce type de situation peut être la planification d'horaire d'examens, le regroupement d'animaux ou la façon de placer des invités autour d'une table. Souvent, dans ce type de graphe, un sommet représente un élément impliqué, et une arête, une incompatibilité entre deux de ces éléments.

Le nombre chromatique est en fait le nombre minimal de couleurs différentes nécessaires pour colorer tous les sommets de ce graphe sans que deux sommets adjacents aient la même couleur.

Étapes de résolution d'un problème avec l'utilisation du nombre chromatique :

1. Représenter la situation à l'aide d'un graphe dans lequel les arêtes représentent les incompatibilités.

2. Énumérer tous les sommets du graphe et les placer en ordre décroissant de degré. Pour deux sommets ayant le même degré, l'ordre n'a pas d'importance.

3. Attribuer une première couleur au sommet ayant le plus grand degré.

4. Colorier les sommets adjacents au sommet de plus haut degré à l'aide d'une autre couleur. Si dans le processus deux sommets ajdacents auraient la même couleur, utiliser une autre couleur.

5. Colorier les autres sommets à l'aide des couleurs déjà utilisés, si possible. Sinon, utiliser une autre couleur.

6. Trouver le nombre chromatique du graphe en comptant le nombre de couleurs utilisées et répondre à la question.

 

Incompatibilités d'horaire

Un directeur d'école souhaite offrir aux employés de son école une formation. Cependant, il remarque qu'il y a plusieurs contraintes et qu'il est impossible de trouver un moment où il pourrait regrouper tout le monde en même temps. Il devra donc offrir la même formation, mais à plusieurs moments différents.

- Les enseignants ont un horaire incompatible avec celui des surveillants.
- Les secrétaires ne peuvent pas assister à la formation au même moment que les directeurs adjoints et que les enseignants.
- Les employés de soutien ont un horaire incompatible avec celui des surveillants.
- Les préposés à l'entretien ne peuvent pas assister à la formation au même moment que les enseignants et que les secrétaires.

Quel est le nombre minimal de formations que le directeur doit prévoir?

Solution

1. Représenter la situation à l'aide d'un graphe dans lequel les arêtes représentent les incompatibilités.



2. Énumérer tous les sommets du graphe et les placer en ordre décroissant de degré.
Enseignants (3) et Secrétaires (3)
Préposés à l'entretien (2) et Surveillants(2)
Employés de soutien (1) et Directeurs adjoints (1)

3. Attribuer une première couleur au sommet ayant le plus grand degré.
Le sommet "Enseignants" et le sommet "Secrétaires" sont les sommets ayant le plus grand degré, soit 3. On choisit alors l'un ou l'autre des sommets comme point de départ. Prenons le sommet "Enseignants" et attribuons lui la couleur rouge.

4. Colorier les sommets adjacents au sommet de plus haut degré à l'aide d'une autre couleur. Si dans le processus deux sommets ajdacents auraient la même couleur, utiliser une autre couleur.
On peut maintenant colorer les sommets adjacents au sommet "Enseignant" à l'aide d'une autre couleur; prenons la couleur bleu. Commençons par le sommet "Surveillant". On peut ensuite colorer le sommet "Secrétaires" en bleu également. On ne peut cependant pas colorer le sommet "Préposé à l'entretient" en bleu, car il est adjacent au sommet "Secrétaires". Nous devons donc utiliser une troisième couleur. Prenons le vert!

5. Colorier les autres sommets à l'aide des couleurs déjà utilisés, si possible. Sinon, utiliser une autre couleur.
Les sommets restants sont "Employés de soutien" et "Directeur adjoint". Comme ces sommets ne sont liés qu'à des sommets bleus et qu'ils ne sont pas lié entre eux, on peut les colorer soit en rouge ou en vert; prenons le rouge.

Voici donc notre graphe coloré représentant la situation.



6. Trouver le nombre chromatique du graphe en comptant le nombre de couleurs utilisées et répondre à la question.
Le nombre de couleurs utilisées dans le graphe, c'est-à-dire le nombre chromatique, est 3. Il faudra donc que le directeur planifie 3 moments différents pour offrir la formation aux employés de l'école.

Les vidéos
Les exercices
Les références