Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

. Les graphes Niveau terminale ES Nathalie DAVAL http://mathematiques.daval.fre

. Les graphes Niveau terminale ES Nathalie DAVAL http://mathematiques.daval.free.fr Université de la Réunion - IREM - Juillet 2012. Table des matières 1 Programme de terminale ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Mise en place : exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.a Introduction historique 3 2.b Le loup, la biche et le chevalier 4 2.c Les ponts du Königsberg 4 2.d Le coloriage de la carte de la Réunion 5 2.e Un trajet minimal 5 2.f Quel labyrinthe ! ! ! 6 2.g Au pays d’Oz 6 2.h L’énigme des trois maisons 7 3 Vocabulaire des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.a Graphe non orienté 9 3.b Ordre et degré 10 3.c Chaîne et cycle 10 3.d Structure de graphes particuliers 11 3.e Distance et diamètre 12 3.f Matrice d’adjacence d’un graphe 12 3.g Graphe orienté 14 3.h Le loup, la biche et le chevalier. . . solution 14 i ii 4 Graphes et chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.a Graphes eulériens 17 4.b Théorème d’Euler 18 4.c Retour à Königsberg 20 5 Graphes et couleurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.a Déﬁnition 21 5.b Coloration minimale 21 5.c Algorithme de coloration de Welsh et Powell 23 5.d Coloration de la carte de la Réunion 24 6 Graphes et trajets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.a Graphes valués 27 6.b Recherche du plus court trajet 28 6.c Allons de la Rivière à la Montagne ! 29 7 Graphes et étiquettes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 7.a Graphes étiquetés 33 7.b Labyrinthe 34 8 Graphes et probabilités. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 8.a Graphes probabilistes 35 8.b Matrice de transition 36 8.c État probabiliste à la ne étape 36 8.d État stable 37 8.e Cas particulier de la recherche d’un état stable à deux états 38 8.f Retour au pays Oz 39 9 Graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 9.a Déﬁnition 41 9.b Théorème d’Euler 41 9.c Critères de planarité 43 9.d Trois maisons, trois installations 45 1 Programme de terminale ES Ce document constitue un cours sur les graphes du niveau de l’option de la terminale ES : on y trouvera tout d’abord quelques exemples « de la vie courante » ainsi que le vocabulaire de base, puis les diﬀérentes utilisations pratiques des graphes : • recherche de l’existence d’une chaîne ou d’un cycle Eulérien, • coloration d’un graphe, • recherche d’une plus courte chaîne d’un graphe pondéré, • caractérisation des mots reconnus par un graphe étiqueté, • recherche d’un état stable d’un graphe probabiliste, • caractérisation des graphes planaires (hors programme, mais intéressant!). Voici un extrait du B.O. N ˚4 du 30 août 2001 concernant l’enseignement de spécialité de mathématiques : ENSEIGNEMENT DE SPÉCIALITÉ Trois domaines sont abordés dans l’enseignement de spécialité : deux d’entre eux (suites et géométrie dans l’espace) prolongent directement le travail commencé en classe de première ; les paragraphes qui suivent expliquent le choix du troisième domaine et de la méthode de travail proposée. Une ouverture sur la théorie des graphes Ce choix est cohérent tant avec le programme de la classe antérieure qu’avec les exigences de formation ultérieure : on trouve en eﬀet ici quelques applications intéressantes du calcul matriciel développé dans l’option de première ES ; par ailleurs, les problèmes résolus constituent une première approche, volontairement modeste, de situations complexes (d’ordonnancement, d’optimisation de ﬂux, de recherche de ﬁchiers informatiques, d’études de migrations de populations. . .) auxquelles de nombreux élèves seront par la suite confrontés, notamment en gestion ou en informatique. Ce thème sensibilise naturellement à l’algorithmique et, en montrant la puissance de la théorie des graphes pour la modélisation, permet un autre regard mathématique sur diverses situations. Enﬁn, la présence des graphes dans les programmes permettra ultérieurement de déﬁnir des thèmes de TPE faisant intervenir des mathématiques consistantes. Un travail axé sur la seule résolution de problèmes Il n’est pas question de retomber dans les pièges du langage ensembliste des années 1970 : toute présentation magistrale ou théorique des graphes serait contraire au choix fait ici. L’essentiel du travail réside dans la résolution de problèmes : résolution à l’initiative des élèves, avec ses essais et tâtonnements, ses hésitations pour le choix de la représentation en termes de graphe (quels objets deviennent arêtes ? lesquels deviennent sommets ?), la recherche d’une solution et d’un raisonnement pour conclure. Toute notion relative à la théorie des graphes absente de la liste de vocabulaire élémentaire du tableau ci-après est clairement hors programme. Cette liste doit suﬃre pour traiter tous les exercices proposés. 1 2 On trouvera dans le document d’accompagnement des éléments de théorie des graphes nécessaires à la formation des enseignants ainsi qu’une liste d’exemples sans caractère normatif, couvrant largement le programme et illustrant le type de travail attendu ; chaque exemple est suivi d’une liste de contenus (termes ou propriétés) que celui-ci permet d’aborder ; un lexique en ﬁn de ce document reprend la totalité des termes et propriétés du programme ainsi introduits. L’optique première étant la résolution de problèmes, on insistera plus sur le bon usage des mots que sur leur déﬁnition formelle. L’intérêt du lexique est de bien marquer des limites à ce qui est proposé. À titre indicatif, la répartition horaire entre les diﬀérents chapitres peut être : 40% pour les graphes ; 35% pour les suites ; 25% pour la géométrie dans l’espace. CONTENU MODALITÉS DE MISE EN ŒUVRE COMMENTAIRES Résolution de problèmes à l’aide de graphes Résolution de problèmes conduisant à la modélisation d’une situation par un graphe orienté ou non, éventuel- lement étiqueté ou pondéré et dont la solution est associée : - au coloriage d’un graphe, - à la recherche du nombre chroma- tique, - à l’existence d’une chaîne ou d’un cycle Eulérien, - à la recherche d’une plus courte chaîne d’un graphe pondéré ou non, - à la caractérisation des mots re- connus par un graphe étiqueté et, ré- ciproquement, à la construction d’un graphe étiqueté reconnaissant une fa- mille de mots. - à la recherche d’un état stable d’un graphe probabiliste à 2 ou 3 sommets. Les problèmes proposés mettront enjeu les graphes simples, la réso- lution pouvant le plus souvent être faite sans recours à des algorithmes. On indiquera que pour des graphes complexes, des algorithmes de réso- lutions de certains problèmes sont absolument nécessaires. On présentera un algorithme simple de coloriage des graphes et un algo- rithme de recherche de plus courte chaîne. Il s’agit d’un enseignement entière- ment fondé sur la résolution de pro- blèmes. L’objectif est de savoir modéliser des situations par des graphes et d’identiﬁer en terme de propriétés de graphes la question à résoudre. Ces algorithmes seront présentés dans les documents d’accompagne- ment et on restera très modeste quant à leurs conditions de mise en œuvre. Vocabulaire élémentaire des graphes : sommets, sommets adjacents, arêtes, degré d’un sommet, ordre d’un graphe, chaîne, longueur d’une chaîne, graphe complet, distance entre deux sommets, diamètre, sous-graphe stable, graphe connexe, nombre chromatique, chaîne eulé- rienne, matrice associée à un graphe, matrice de transition pour un graphe pondéré par des probabilités. Les termes seront introduits à l’oc- casion de résolution uploads/Science et Technologie/ cours-graphes-ensias-shit-fuc-pdf.pdf