Remerciez-le!

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

6 E Ex xe er rc ci ic ce es s … … Dans les exemples ci-dessous, on a parfois co

6 E Ex xe er rc ci ic ce es s … … Dans les exemples ci-dessous, on a parfois construit les graphes et donné quelques éléments de réponse afin d'avoir assez vite une idée générale de ce qui est proposé : on indique aussi les contenus illustrés ou introduits dans chacun des exemples proposés. La théorie des graphes est rarement abordée en France dans le cursus universitaire des enseignants : il s'agit donc d'une nouveauté pour la plupart d'entre eux. Néanmoins, comme s'exerce dans ce domaine un mode de pensée auquel ils sont habitués, ils peuvent envisager cet enseignement sans inquiétude, tant pour eux-mêmes que pour leurs élèves. Exemple 1 : les enveloppes Peut-on parcourir une fois et une seule les arêtes des graphes ci-dessous sans lever le crayon ? • Contenu : introduction des graphes (arêtes, sommets, ordre, sommets adjacents) ; degré d’un sommet ; chaîne eulérienne ; théorème d’Euler. Exemple 2 : les ponts de Königsberg Au XVIIIème siècle, les habitants de Königsberg (actuellement Kaliningrad, région de la Russie frontalière de la Pologne et de la Lituanie) aimaient se promener le dimanche. La ville de Königsberg comprenait 7 ponts, disposés selon le schéma ci-dessous. Le souhait des habitants de Königsberg était de faire un trajet passant une fois et une seule par chaque pont. Comment faire ? • Contenu : introduction des graphes (arêtes, sommets, ordre, sommets adjacents) ; degré d’un sommet ; cycle eulérien. Exemple 3 : dominos Peut-on aligner tous les pions d’un jeu de domino suivant la règle du domino ? On commencera par étudier la question avec un jeu dont les dominos comportent les chiffres jusqu'à n, pour n=2,3,4. Une arête représente un domino. Il faut trouver une chaîne qui permet de parcourir toutes les arêtes une fois et une seule. On ne s’est pas occupé ici des «doubles » puisqu'on peut toujours les intercaler. • Contenu : graphes complets ; chaînes eulériennes ; degré d’un sommet ; théorème d’Euler. 7 Exemple 4 : traversée de frontières Cinq pays sont représentés ci-contre avec leurs frontières. Est-il possible de partir d'un pays et d’y revenir en franchissant chaque frontière une fois et une seule ? • Contenu : chaîne eulérienne ; degré d’un sommet ; théorème d’Euler. Exemple 5 : dessins de graphes -Parmi les graphes ci-dessous, déterminer ceux qui sont susceptibles de décrire une même situation. - Peut-on dessiner des graphes simples (pas d’arêtes dont les extrémités sont confondues, et au plus une arête joignant deux sommets) dont la liste des degrés des sommets soit : 6-3-2-2-1-1-1 7-5-3-2-2-2-2-2 • Contenu : représentations de graphes ; degrés de sommets. Exemple 6 : associer un graphe à une situation Comparer les trois graphes définis ci-dessous : - on considère un octaèdre ; un sommet du graphe est associé à un sommet de l’octaèdre et une arête correspond à une arête de l’octaèdre ; - on considère un cube ; un sommet du graphe est associé à une face du cube et deux sommets du graphe sont reliés par une arête si les faces correspondantes ont une arête commune ; - les sommets du graphe sont tous les sous-ensembles à deux éléments de {1,2,3,4} ; deux sommets sont reliés si leur intersection est non vide ; Représenter la situation ci-dessous à l’aide d’un graphe : Trois pays envoient chacun à une conférence deux espions ; chaque espion doit espionner tous les espions des autres pays. • Contenu : représentations de graphes ; sommets, sommets adjacents ; arêtes. 8 Exemple 7 : matches de football Une ligue de football comporte 5 équipes. - il est décidé par le bureau de la ligue que lors d’un week-end d’entraînement, chaque équipe jouera quatre matches (deux équipes ne peuvent pas se rencontrer plus d’une fois). Comment l’organiser (chacun est libre de ses règles d’organisation) ? - le calendrier étant trop chargé, les organisateurs décident que chaque équipe ne jouera que trois matches. Comment l'organiser ? • Contenu : degré d’un sommet ; lien entre la somme des degrés des sommets et le nombre d’arêtes. Exemple 8 : poignées de main M. et Mme Euler assistent à une réunion. Il y a trois autres couples dans l'assistance et plusieurs poignées de mains sont échangées. Personne ne serre sa propre main et les époux ne se serrent pas la main. Deux personnes quelconques de l’assemblée se serrent la main au plus une fois. M. Euler constate que les 7 autres personnes ont échangé des poignées de mains en nombres tous distincts. Combien de poignées de mains M. et Mme Euler ont-ils échangé avec les autres membres de la réunion ? Une personne peut serrer la main d'au plus 6 autres personnes. Pour que le nombre de poignées de mains échangées soient tous distincts, il s’agit nécessairement des nombres 6, 5, 4, 3, 2, 1 et 0. Une personne a échangé 6 poignées de main ; c’est donc son conjoint qui n’en a échangé aucune. Une personne échange 5 poignées de mains ; c’est donc son conjoint qui en échange une seule. Une des personnes des deux couples non encore considérés échange 4 poignées de main, donc son conjoint en échange 2. Que reste-t-il pour le dernier couple ? • Contenu : introduction des graphes (arêtes, sommets, ordre, sommets adjacents) ; degré d’un sommet. Exemple 9 : transport de produits chimiques On trouvera ci-après le graphe d’incompatibilité de six produits chimiques. Quel est le nombre minimum de wagons nécessaires à leur transport ? • Contenu : nombre chromatique. 9 Exemple 10 : coloration de la carte de l’Europe On veut colorer chaque pays de la carte ci-dessous de telle sorte que deux pays voisins ne soient pas de la même couleur. Montrer qu’il faut disposer d’au moins quatre couleurs et que quatre couleurs suffisent. (Deux pays dont les frontières n’ont qu’un nombre fini de points communs ne sont pas considérés comme voisins). F B H A S I E Au P T Lu • Contenu : sous–graphe complet ; nombre chromatique. Exemple 11 : un problème d’aquariophile A, B, C, D, E, F, G et H désignent huit poissons ; dans le tableau ci-dessous, une croix signifie que les poissons ne peuvent cohabiter dans un même aquarium : A B C D E F G H A × × × × × B × × × × C × × × × × D × × × × E × × × × F × × × G × × × × H × × × Quel nombre minimum d’aquariums faut-il ? • Contenu : matrice associée à un graphe ; sous-graphe ; graphe complet ; nombre chromatique. 10 Exemple 12 : nombre chromatique Tracer les graphes associés aux matrices ci-dessous et chercher leur nombre chromatique. A =               0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 B =           0 1 0 1 0 1 0 1 0 C =                 0 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 1 0 Les graphes ci-dessous peuvent-ils être associés à C ? Donner des matrices associées au graphe suivant : • Contenu : matrices et graphes associés ; nombre chromatique. Exemple 13 : organisation d’un examen On veut organiser un examen comportant, outre les matières communes, 6 matières d’options : Français (F), Anglais (A), Mécanique (M), Dessin industriel (D), Internet(I), Sport (S) ; les profils des candidats à options multiples sont : F,A,M D,S I,S I,M 1 - Quel est le nombre maximum d’épreuves qu’on peut mettre en parallèle ? 2 - Une épreuve occupe une demi-journée ; quel est le temps minimal nécessaire pour ces options ? Solution Le graphe associé à cette situation est le suivant : 1- Tout sous-graphe de plus de trois sommets comporte des arêtes ; deux sous- graphes d’ordre trois (de sommets respectivement A,D,I et F,D,I) n’ont pas d’arêtes : le nombre maximum d’épreuves en parallèle est 3. 2- Il y a un sous-graphe complet d’ordre 3 ; le nombre chromatique est au moins égal à 3 ; on voit que 3 couleurs suffisent. • Contenu : sous-graphes ; graphe complet ; nombre chromatique. 11 Exemple 14 : ouverture de magasins Une chaîne de cinq magasins décide d'ouvrir ses magasins en nocturne avec les contraintes suivantes : les deux premiers magasins ne peuvent pas être ouverts ensemble ; il en est de même pour les deux derniers ; au plus un seul magasin peut être ouvert parmi les magasins 1, 3, 4. Trouver un état qui maximise le nombre de magasins ouverts en nocturne, tout en respectant les contraintes. Solution Il n’y a qu’un seul sous-graphe a trois éléments sans arêtes ; tous les sous-graphes d’ordre 4 ou uploads/Geographie/ graphes-exos.pdf