LES GRAPHES. Introduction L'introduction d'éléments de la théorie des graphes dans...

LESLES GRAPHESGRAPHES

IntroductionIntroductionL'introduction d'éléments de la théorie des graphes dans l'enseignement de spécialité de la classe terminale de la série ES constitue une grande nouveauté : cette branche des mathématiques discrètes fait son entrée dans l'enseignement secondaire français le travail proposé est axé sur la seule résolution de problèmes et aucunement sur un exposé magistral.

Pourquoi introduire des Pourquoi introduire des éléments sur les graphes ?éléments sur les graphes ? Donner continuité et cohérence avec le

programme 1ère S’ouvrir à de nouveaux raisonnements,

s’entraîner à avoir un autre regard mathématique Montrer des mathématiques non classiques liées

à des problèmes concrets Sensibiliser à l’algorithmique Réinvestir ce travail dans les T.P.E.

Pourquoi axer le travail sur la Pourquoi axer le travail sur la seule résolution de problèmes ?seule résolution de problèmes ?

Ouvrir un grand champ de modélisation conduisant à des solutions efficaces pour de nombreux problèmes

Laisser place à l'initiative des élèves, avec un temps nécessaire de tâtonnements et d’essais

LeLe programmeprogramme

Modeste : Le temps consacré à l'étude de ces notions, pourrait représenter 40% du temps total, soit environ 24 heures.

Contenu théorique réduit : L'optique étant la résolution de problèmes, c'est le bon usage des notions relatives aux graphes, et non la mémorisation de définitions formelles, qui est ici recherchée.

Les Graphes : Et si ça servait Les Graphes : Et si ça servait à quelque chose ?à quelque chose ?La théorie des graphes possède de nombreuses applications et intervient dans des domaines variés comme :

La ChimieLa PhysiqueLa BiologieL’InformatiqueLes Mathématiques

Les Sciences socialesL’IndustrieLa GéographieL’Architecture

Exemple 1: Exemple 1: Somme des degrés des sommets Somme des degrés des sommets d ’un graphed ’un graphe

Un tournoi d’échec oppose n personnes. Chaque joueur doit rencontrer tous les autres participants.Représenter cette situation par un graphe pour : n = 4 n = 5 n = 6 Combien doit-on prévoir de rencontres ?

Propriété : La somme des degrés d’un GNO est égale à deux fois le nombre d’arêtes.

n = 4 : d = 4 3 = 12. Il y aura 6 matchs. n = 5 : d = 5 4 = 20. Il y aura 10 matchs. n = 6 : d = 6 5 = 30. Il y aura 15 matchs.

n = 4

n = 5

n = 6

Maurice, le facteur doit effectuer sa tournée. Il doit s’arrêter à la Poste (P), la Gare (G), la Mairie (M), le Lycée (L), le Centre commercial (C) et distribuer le courrier dans les rues 1 à 7. Il doit définir son trajet en respectant les contraintes ci-dessous : 

Exemple 2: Exemple 2:

Chaînes eulériennes.Cycles eulériensChaînes eulériennes.Cycles eulériens

1. Trouvera-t-il un circuit sans repasser dans la même rue ?

Ici, le facteur peut suivre la chaîne eulérienne: 4 3 2 4 1 2 5 1 mais est obligé de partir du lycée.Il n’existe pas ici de cycle eulérien.Si le facteur ne distribuait pas le courrier de la rue 4, il pourrait effectuer un cycle eulérien: 3 4 2 5 1 2 3 ( par exemple )

Théorème d’Euler : Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est 0 ou 2. Un graphe connexe admet un cycle eulérien si et seulement si ses sommets sont de degré pair.

A =

0 0 0 1 10 0 1 1 10 1 0 1 01 1 1 0 11 1 0 1 0

Propriété : Soit A la matrice associée à un graphe. Le terme aij de la matrice An donne le nombre de chaînes de longueur n reliant i à j.

2 2 1 1 12 3 1 2 11 1 2 1 21 2 1 4 21 1 2 2 3

A2 =

2 3 3 6 53 4 5 7 73 5 2 6 36 7 6 6 75 7 3 7 4

A3 =

Exemple 3:Exemple 3:Recherche du plus court cheminRecherche du plus court cheminPour rentrer chez lui, Maurice doit se rendre de la poste à la gare. Quel est le plus court chemin qu’il peut suivre ?

10801090

800(P)

680(P)

++

1090

800(P)

680(P)

1280(L)

1880(L)

1410(L)1090

800(P)

680(P)

1280(L)

1880(L)

1400(M)

1890(M)

1090

800(P)

680(P)

1280(L)

1880(L)

1890(M)

1870(C)

1090

800(P)

680(P)

1280(L)

1870(C)

Maurice se rendra de la poste à la gare en passant par la Mairie : la distance parcourue sera 1870 m.

1090

Cinq étudiants doivent passer des écrits d ’examen.

Maxime en Anglais, Physique, Mathématiques Aude en Espagnol, Biologie, Mathématiques Marion en Mathématiques, Français, Anglais Amélie en Anglais, Biologie Laurent en Physique, Français

Exemple 4:Exemple 4:Coloration d ’un grapheColoration d ’un graphe

Si chaque écrit dure 1/2 journée, quel nombre minimal de jours doit-on prévoir?

Sommet M A P F B E

Ordre 5 4 3 3 3 2

Couleur R

Sommet M A P F B E

Ordre 5 4 3 3 3 2

Couleur R J J

Sommet M A P F B E

Ordre 5 4 3 3 3 2

Couleur R J V V J

Sommet M A P F B E

Ordre 5 4 3 3 3 2

Couleur R J V B V J

En appliquant l ’algorithme de coloration, il a fallu quatre couleurs pour colorier ce graphe.

Comme (A,F,M,P) forme un sous-graphe complet d ’ordre 4,

le nombre chromatique de ce graphe est 4.

Il faudra donc 4 jours pour organiser cet examen.

An: l ’électeur est favorable à la liste A au n-ieme jour de campagne; probabilité pn Bn: l ’électeur est favorable à la liste B au n-ieme jour de campagne; probabilité qn

Exemple 5:Exemple 5:Graphe probabilisteGraphe probabiliste

A Clochemerle, la campagne électorale fait rage: deux listes A et B s ’affrontent. Chaque jour de campagne on interroge un électeur pris au hasard et on définit les événements suivants:

A l ’issue de chaque jour de campagne, 20% des électeurs favorables à la liste A et 30% des électeurs favorables à la liste B changent d ’avis le jour suivant.

Le graphe probabiliste qui décrit cette situation est:

A B0,8 0,7

0,2

0,3

La matrice de transitionde ce graphe est:

7,03,0

2,08,0M

L ’état probabiliste au premier jour de la campagne est la matrice ligne 111 qpP

L ’état probabiliste Pn à l ’étape n est:

1

11 7,03,0

2,08,0

n

nn qpqp

L ’état Pn à l ’étape n, converge vers un état P indépendant de l ’état initial et on a P=PM, soit:

03,02,07,03,0

2,08,0

qpqpqp

Comme p+q=1 alors

p=0,6 et q=0,4

La liste A gagnera l ’élection.