Remerciez-le!

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

Équipe académique Mathématiques page 2 Bordeaux Table des matières EXTRAIT DU P

Équipe académique Mathématiques page 2 Bordeaux Table des matières EXTRAIT DU PROGRAMME DE SPÉCIALITÉ DE TERMINALE ES --------------------- 4 I THÉORÈME D’EULER--------------------------------------------------------------------------- 5 A Quelques définitions ---------------------------------------------------------------------------------------------- 5 B Théorème d’Euler-------------------------------------------------------------------------------------------------- 5 C Exercices 6 II DES DEGRÉS ET DES GRAPHES ---------------------------------------------------------- 8 A Quelques propriétés ---------------------------------------------------------------------------------------------- 8 B Exercices 8 III COLORATION-------------------------------------------------------------------------------------- 9 A Quelques définitions ---------------------------------------------------------------------------------------------- 9 B Nombres chromatiques de quelques graphes-------------------------------------------------------------10 C Propriétés 10 D Algorithme de coloration de Welsh et Powell --------------------------------------------------------------11 E Le grand théorème de coloration -----------------------------------------------------------------------------11 F Exercices 12 G Corrigés des exercices ------------------------------------------------------------------------13 IV MATRICE ASSOCIÉE À UN GRAPHE---------------------------------------------------- 17 A Problème 17 B Définition et propriété --------------------------------------------------------------------------------------------17 C Exercices 18 V MEILLEURS CHEMINS------------------------------------------------------------------------ 19 A Exemple 19 B Quelques définitions ---------------------------------------------------------------------------------------------19 C Algorithme de Dijkstra -------------------------------------------------------------------------------------------20 D Exercices 20 VI MATRICES DE TRANSITION---------------------------------------------------------------- 21 A Problème 21 B Prolongements ----------------------------------------------------------------------------------------------------22 C Cas général 22 D Exercices 23 VII AUTOMATES------------------------------------------------------------------------------------- 24 A Premières notions ------------------------------------------------------------------------------------------------24 Équipe académique Mathématiques page 3 Bordeaux B Étude d’un exemple ----------------------------------------------------------------------------------------------24 C Exercices 25 D Corrigés des exercices ------------------------------------------------------------------------------------------26 BIBLIOGRAPHIE – LIENS -------------------------------------------------------------------------- 27 Avertissement Ce présent document a été inspiré par des travaux de : ♦ Marie Mégard, IA-IPR ; nous avons recopié certains paragraphes d'un document dont elle est l'auteur et que l'on peut télécharger à l’adresse : http://www.apmep.asso.fr/CL02gra.pdf ; ♦ Éric Sopéna, professeur à Bordeaux 1, qui participe à l’animation de ce stage. Équipe académique Mathématiques page 4 Bordeaux Extrait du programme de spécialité de Terminale ES BO hs n°4 du 30 août 2001 CONTENUS 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, éventuellement étiqueté ou pondéré et dont la solution est associée : - au coloriage d’un graphe, - à la recherche du nombre chromatique, - à 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 reconnus par un graphe étiqueté et, réciproquement, à la construction d’un graphe étiqueté reconnaissant une famille de mots, - à la recherche d’un état stable d’un graphe probabiliste à 2 ou 3 sommets. Les problèmes proposés mettront en jeu des graphes simples, la résolution pouvant le plus souvent être faite sans recours à des algorithmes. On indiquera que, pour des graphes complexes, des algorithmes de résolution de certains problèmes sont absolument nécessaires. On présentera un algorithme simple de coloriage des graphes et un algorithme de recherche de plus courte chaîne. Il s’agit d’un enseignement entièrement fondé sur la résolution de problèmes. L’objectif est de savoir modéliser des situations par des graphes et d’identifier en terme de propriétés de graphes la question à résoudre. Ces algorithmes seront présentés dans les documents d’accompagnement 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’occasion de résolution de problèmes et ne feront pas l’objet d’une définition formelle, sauf lorsque cette définition est simple et courte (degré d’un sommet, ordre d’un graphe par exemple). Les élèves devront savoir utiliser à bon escient le vocabulaire élémentaire des graphes, vocabulaire qui sera réduit au minimum nécessaire à la résolution des problèmes constituant l’enseignement de cette partie. Résultats élémentaires sur les graphes : - lien entre la somme des degrés des sommets et le nombres d’arêtes d’un graphe ; - conditions d’existence de chaînes et cycles eulériens ; - exemples de convergence pour des graphes probabilistes à deux sommets, pondérés par des probabilités. On pourra dans des cas élémentaires, interpréter les termes de la puissance nième de la matrice associée à un graphe. Équipe académique Mathématiques page 5 Bordeaux I Théorème d’Euler A Quelques définitions Un graphe est constitué d’un nombre fini de sommets et d’arêtes, s’il est non orienté ; de sommets et d’arcs, s’il est orienté. L’ordre d’un graphe est le nombre de sommets de ce graphe. Le degré d’un sommet est le nombre d’arêtes ayant ce sommet pour extrémité. Une boucle augmente de deux le degré d’un sommet. Une chaîne est une suite alternée de sommets et d'arêtes. La longueur d’une chaîne est le nombre d’arêtes qui la composent. La distance entre deux sommets est la plus courte longueur des chaînes qui les relient. Le diamètre d’un graphe est la plus grande distance entre entre deux sommets. Un cycle est une chaîne dont les arêtes sont distinctes et dont l'origine et l'extrémité sont confondues. Une chaîne eulérienne est une chaîne empruntant une fois et une seule chaque arête du graphe. Un cycle eulérien est un cycle empruntant une fois et une seule chaque arête du graphe. Un graphe est connexe si pour toute paire de sommets du graphe il existe une chaîne les reliant. B Théorème d’Euler Théorème a) Un graphe connexe admet une chaîne eulérienne si et seulement si tous ses sommets sont de degré pair sauf éventuellement deux d’entre eux. b) Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair. La condition est nécessaire Cas de la chaîne On considère un sommet qui n’est pas une extrémité : chaque fois que la chaîne passe par ce sommet, elle l’atteint par une arête et en repart par une autre. Comme chaque arête est utilisée dans la chaîne une fois et une seule, chaque arête incidente à ce sommet peut être associée à une autre arête incidente à ce même sommet. Donc tous les sommets sont pairs sauf éventuellement les deux extrémités. composantes connexes graphe connexe graphe non connexe Équipe académique Mathématiques page 6 Bordeaux Cas du cycle Un cycle n'étant qu'un cas particulier de chaîne, le raisonnement ci-dessus vaut pour un cycle, le cas particulier des extrémités étant exclu. Remarque : la plupart du temps, seule cette propriété "directe" sera mise en œuvre, sous sa forme contraposée. La condition est suffisante La partie réciproque du théorème est un peu plus délicate à démontrer. Mais elle présente l'avantage de fournir un procédé de construction d'un cycle eulérien, et à ce titre mérite peut-être d'être exposée aux élèves sur un exemple. De plus, l'utilisation de sous-graphes est efficace pour la résolution de nombreux problèmes, et à ce titre a valeur de méthode. Notons tout d'abord que le a) du théorème se déduit du b) aisément : si deux sommets seulement sont de degré impair, on peut les relier provisoirement par une arête et mettre en œ uvre le b). le cycle obtenu sera transformé en simple chaîne par suppression de l'arête rajoutée au début. Soit donc un graphe G dont tous les sommets sont de degré pair. Choisissons un sommet A1 et une arête incidente à A1, puis considérons l’autre extrémité de cette arête : ce deuxième sommet étant de degré pair, on peut en repartir par une autre arête, et atteindre un « autre » sommet. Si ce dernier est différent de A1, on peut en repartir à nouveau (car son degré est pair). Ainsi de suite. Comme le graphe possède un nombre fini d'arêtes, la chaîne ainsi formée se referme tôt ou tard en A1, formant un cycle C1. Ce cycle peut être eulérien (s'il utilise toutes les arêtes du graphe). Dans le cas contraire, chacune des composantes restantes vérifie les hypothèses du théorème : elle est finie, connexe, et ses sommets sont de degré pair. De plus, comme le graphe G est connexe, chacune des composantes restantes possède au moins un sommet appartenant à C1. Choisissons un tel sommet A2 pour une des composantes restantes : le même procédé de construction développé plus haut permet d'obtenir un nouveau cycle C2 contenant A2. On peut l'insérer dans le cycle C1 au niveau de A2. L'itération de ce procédé jusqu'à épuisement des arêtes, qui est certain puisque le graphe est fini, permet d'écrire pour G un cycle eulérien. C Exercices A1 A2 C2 C1 A2 Équipe académique Mathématiques page 7 Bordeaux Exercice 1 Est-il possible de tracer les figures suivantes sans lever le crayon (et sans passer deux fois sur le même trait !…) ? Pourquoi ? Exercice 2 On considère des dominos dont les faces sont numérotées 1, 2, 3, 4 ou 5. 1) En excluant les dominos doubles, de combien de dominos dispose-t-on ? 2) Montrez que l’on peut arranger ces dominos de façon à former une boucle fermée (en utilisant la règle habituelle de contact entre les dominos). 3) Pourquoi n’est-il pas nécessaire de considérer les dominos doubles ? 4) Si l’on prend maintenant des dominos dont les faces sont numérotées de 1 à n, est-il possible de les arranger de façon à former une boucle fermée ? Exercice 3 Est-il possible de se promener dans chacune de ces maisons en passant une uploads/Management/ graphes-02-03-pdf.pdf