Aller au contenu principal

3.4 – L'optimisation à l'aide des Graphes

Avant de lire cette section, tentez de répondre aux question de l'Activité 1 à la page 46 du manuel Vision Vol. 2. Vous aurez un bon aperçu de la matière que nous aborderons dans cette section.

3.4.1 – Recherche de la solution optimale (maximum et minimum)​

Comme nous l'avons vu plus tôt cette année, l'optimisation a comme objectif de trouver la solution maximale ou minimale d'une situation (dépendant des objectifs). Les graphes pourront être utilisés d'une manière similaire pour nous aider à déterminer la solution (réelle ou pas) d'une suite d'évènements.

Pour déterminer la valeur d'un chemin, d'un cycle ou tout autre combinaison de sommets, une stratégie intéressante pourrait être d'inscrire sur chaque sommet emprunté la valeur du chemin jusqu'à ce point. Ainsi, on pourra mieux évaluer nos options et éviter le travail en double.

Voici un exemple :

Considérons la situation suivante: Quel est le temps minimal pour passer du sommet A au sommet E? Les temps reliés à chaque arêtes sont inscrits en minutes

Graphe valué à 5 sommets A, B, C, D, E avec les valeurs cumulatives des chemins indiquées sur chaque sommet

Ici, on peut voir les valeurs cumulatives des arêtes indiquées sur chacun des sommets. On remarque que certaines chaînes empruntent des arêtes communes. En notant ces valeurs, on évite les démarches dédoublées.

On voit donc que la chaîne la plus courte est la chaîne A-B-C-D-E avec 18 minutes.

3.4.2 – Nombre chromatique​

Dans certaines situations d'optimisation, on cherchera à déterminer le nombre minimal de sommets différents qu'il faut attribuer à un graphe pour éviter que deux sommets de la même «sorte» ne se touchent. On pourrait par exemple penser à déterminer le nombre de stations de breuvages différentes qu'il faut installer lors d'une course pour éviter que des coureurs se fassent offrir deux fois consécutives le même breuvage. Pour visualiser ces situations, on peut utiliser la technique du nombre chromatique.

Pour colorer un graphe et déterminer le nombre chromatique, on peut suivre les trucs suivants :

  • Identifier le sommet ayant le plus grand degré et attribuer une première couleur à ce sommet
  • Identifier le prochain sommet à colorer (encore une fois basé sur le degré) et colorer ce sommet avec une couleur différente
  • Passer aux autres sommets en alternant les couleurs, si les couleurs déjà utilisées ne suffisent plus, utilisez-en une nouvelle.
Exemple d'un graphe correctement coloré avec trois couleurs (rouge, bleu, vert)

Considérons l'exemple suivant :

Déterminer le nombre chromatique du graphe suivant:

Graphe non coloré à six sommets utilisé pour déterminer le nombre chromatique
  1. On identifie le sommet avec le plus haut degré, on le colorera en rouge
Le sommet central de plus haut degré coloré en rouge
  1. Identifier le sommet au plus haut degré relié au sommet rouge, utiliser une nouvelle couleur
Un sommet voisin du sommet rouge coloré en bleu
  1. Procéder vers les autres sommets en alternant les couleurs
Deux autres sommets colorés en vert en alternant avec le rouge et le bleu

Puisque nous avons utilisé 3 couleurs différentes, le nombre chromatique est de 3.

Graphe complètement coloré avec les trois couleurs rouge, bleu et vert, confirmant un nombre chromatique de 3

3.4.3 – Chemin critique​

Vous allez me trouver contradictoire ici : Un chemin critique est un chemin simple de valeur maximale qui permet de déterminer la valeur minimale (temps, distance ou autre) pour réaliser une tâche. Ce que ça veut dire c'est que le temps minimum pour accomplir une tâche correspond à la somme des temps maximums requis pour chacune des étapes (je vais utiliser un exemple pour rendre ça plus évident).

À la manière de la section 3.4.1, on indiquera le temps requis cumulatif sur les sommets pour se simplifier la tâche.

Éléments importants à considérer :

  • Un embranchement signifie que deux tâches (ou séries de tâches) peuvent s'accomplir de manière simultanée
  • Un raccord (plusieurs chemins qui reviennent au même sommet) signifie que toutes les tâches préalables doivent avoir été accomplies pour passer à la prochaine étape.

Voici un exemple :

Pour résoudre une situation problème en mathématique, une équipe d'élèves a une série de tâches à effectuer. Ils représentent ces tâches grâce au graphe suivant. Ils y indiquent sur les arêtes le temps nécessaire pour effectuer chaque tâche.

Quel serait le temps minimum pour qu'ils terminent le problème?

  1. Comme montré précédemment, on fait la somme des durées des arêtes
Graphe des tâches A à I avec les durées cumulatives inscrites sur chaque sommet, montrant deux chemins possibles vers H (49 et 52 minutes)
  1. On rencontre alors un problème!

Lorsqu'on arrive au raccord H, le chemin du haut aura pris 49 minutes alors que le chemin du bas aura pris 52 minutes!

  1. Comme mentionné plus haut, pour déterminer la valeur critique d'un graphe, on cherche à compter le chemin simple ayant la valeur maximale!

Ceci veut dire qu'on ne peut procéder à la dernière étape de l'évaluation si l'étape f n'est pas complétée! Celle-ci prend un total de 52 minutes avant d'être terminée. Il faudra donc compter le chemin A-B-C-E-F-H-I comme le chemin à compter

Graphe complet du chemin critique montrant le chemin A-B-C-E-F-H-I totalisant 62 minutes

On comptera donc 62 minutes pour compléter la situation problème.

Les exercices liés à cette section se trouvent dans le manuel Vision Vol. 2 : p. 52 #1, 3, 4, 5, 7, 9, 10, 12, 13, 15, 17, 18, 19