1 Atelier de formation : MAT - 5104 optimisation II (les graphes). MARTIN FRANCOEUR conseiller en...

1

Atelier de formation : MAT - 5104

optimisation II (les graphes).

MARTIN FRANCOEUR

conseiller en évaluation

( La société GRICS )

martin.francoeur@grics.qc.ca

2

Présentation du programme

• Au secteur des jeunes, le programme de mat 068-514 est divisé en trois parties :– Favoriser chez l ’élève l’utilisation d ’outils

d ’optimisation 50 %– Accroître chez l’élève l’habileté à analyser des

données statistiques ou probabilistes 30 %– Amener l ’élève à analyser des situations

géométriques 20 %

3

suite

• Au secteur des adultes, le programme de 514 est divisé en 4 cours :

– Mat 5101 : optimisation I (Mat 5083)– Mat 5102 : statistique III (nouveau cours)– Mat 5103 : probabilités II (Mat 5084 +)– Mat 5104 : optimisation II (les graphes)

4

Définitions

Graphe

Un graphe est une structure comportant un ensemble de points appelés sommets et un ensemble de lignes appelées arêtes reliant certains ou tous ces sommets deux à deux.

5

Exercice 1

Exercices complémentaires

6

Boucle

• Pour indiquer qu’une arête part d’un sommet et revient à ce même sommet sans relier ce sommet à un autre, nous utilisons une boucle.

• Dans un graphe, il peut y avoir plus d’une boucle par sommet.

7

Degré

• Dans un graphe (avec ou sans boucle), le degré d’un sommet c’est le nombre de fois qu’une arête touche à ce sommet. On note le degré d’un sommet s par d(s).

• Une boucle sur un sommet augmente de deux le degré du sommet, car les deux extrémités de la boucle touchent au même sommet.

8

Graphe orienté

• Un graphe orienté est un ensemble de sommets avec des arcs (prenant la forme de flèches) reliant certains ou tous ces sommets entre eux.

9

Exercice 2

• Exercices complémentaires

10

Chaîne et cycle

• Une chaîne dans un graphe est une suite de sommets qui comporte toujours une arête entre deux sommets consécutifs. La suite est alors décrite de la manière suivante :

(a, b, c, e, …).

• où chaque lettre est un sommet de la chaîne et le fait que deux lettres se suivent indique qu’il y a une arête reliant ces deux sommets.

11

Chaîne et cycle (suite)

• Un graphe est connexe si pour toute paire de sommets distincts a et b dans ce graphe, il existe une chaîne qui va de a à b.

12

Chaîne et cycle (suite)

• Un cycle est une chaîne qui revient à son point de départ.

13

Chaîne et cycle (suite)

• Un cycle simple est un cycle dont toutes les arêtes sont différentes les unes des autres.

14

Exercice 4

• Voir document : exercices complémentaires.

15

Graphe eulérien

• Dans un graphe eulérien, il existe un cycle qui passe par chacune des arêtes du graphe une et une seule fois seulement.

16

Exercices 7 et 8

• Voir document : exercices complémentaires.

17

Théorème 1

• Si un graphe connexe est eulérien, alors tous les sommets de ce graphe sont de degré pair. Réciproquement, si tous les sommets d ’un graphe connexe sont de degré pair, alors ce graphe est eulérien.

18

Graphe hamiltonien

• Un graphe hamiltonien est un graphe pour lequel il existe un cycle qui passe par chacun des sommets du graphe une et une seule fois.

19

Exercice 9

• Voir document : exercices complémentaires.

20

Graphe valué

• Un graphe valué est un graphe pour lequel on associe un nombre plus grand que zéro à chaque arête.

• Quand cela a du sens, la valeur d’une chaîne dans un graphe valué est la somme des valeurs de chacune des arêtes constituant cette chaîne.

21

Exercice 10

• Voir document : exercices complémentaires.

22

Graphe orienté valué et réseau

• Lorsqu’on assigne un nombre plus grand que 0 à chaque arc d’un graphe orienté donné, on dit alors que ce graphe orienté est valué. Ce type de graphe orienté porte un nom spécial.

23

Graphe orienté valué et réseau (suite)

• La méthode pour trouver le chemin le plus court pour exécuter un projet s’appelle la recherche du chemin critique.

24

Graphe orienté valué et réseau (suite)

• Un chemin dans un graphe orienté est une suite de sommets du graphe composée uniquement d’arcs se suivant dans ce graphe. La suite est alors décrite de la manière suivante :

[a, b, c, d, …]

• où a, b, c, d, … sont des sommets du chemin et (a, d), (b, c), (c, d),… sont toujours des arcs du graphe.

25

Graphe orienté valué et réseau (suite)

• La valeur d’un chemin est la somme des valeurs attribuées à chaque arc du chemin.

26

Graphe orienté valué et réseau (suite)

• La démarche suivante permet de trouver le chemin critique dans un réseau.

27

Graphe orienté valué et réseau (suite)

• faire une liste de tous les chemins qui vont du début D à la fin F;

• calculer la valeur de tous ces chemins;

• prendre le chemin (ou un chemin s’il y en a plusieurs) de longueur optimale.

Le chemin trouvé est le (ou un) chemin critique.

28

Un peu d’exercices

• Voici quelques exemples d’optimisation

• Exercice 18

• Exercice 19

• Exercice 23

• Exercice 26