Hors programme lycée / Graphe 57 exercices (dont 51 corrigés)

a
ChingQuizz : 3 exercices disponibles pour l’evaluation par QCM : 1. Partage par niveaux (Algorithme de Bellman dans un graphe sans circuit) E.7675 On considère le graphe orienté ci-dessous : 1 Écrire la matrice d’adjacence associée à ce graphe. 2 Le graphe est-il sans circuit? Si oui, le partager en niveaux et proposer une nouvelle représentation du graphe. E.7678 Dans l’entreprise des maîtres verriers de Bayel, on compte sept ateliers différents utilisés pour la création des pièces. Pour étudier les différents passages d’une pièce d’un atelier à l’autre, on associe une lettre à chacun des ateliers. Atelier Compassage Décors Flettage Moules Sommet C D F M Atelier Polissage Rebrulâge Soufflerie Sommet P R S Le graphe orienté ci-dessous indique les différents passages possibles d’atelier en atelier d’une pièce. 1 En utilisation les sommets des graphes dans l’ordre al-phabétique, déterminer la matrice d’adjacence associée à ce graphe. 2 Le graphe est-il sans circuit? Si oui, le partager en niveaux et donner une nouvelle représentation de ce graphe. E.8188 Un collectif d’amis décide de créer un ˇ Escape Game ı sur Montpellier, cette attraction doit com-porter plusieurs salles dont chacune représentera un thème où une énigme sera à résoudre. 1 Voici la liste des thèmes proposés pour la création de leur attraction : E : l’espace J : la jungle N : la neige S : Sherlock Holmes W : Wall Street M : la mer A : les avions I : l’informatique Ce collectif a imaginé les différentes possibilités de passer d’une pièce à thème à une autre. Ils ont représenté, dans le graphe ci-dessous, ces passages ci-dessous par les arêtes orientées : a En rangeant les sommets dans l’ordre alphabétique, donner la matrice d’adjacence associée à ce graphe. b Ce graphe est-il sans circuit? Si oui, le partager en niveaux et proposer une nouvelle présentation pour ce graphe. 2 Dans la salle ˇ Espace ı, est présentée la constellation de la grande Ourse composée de 7 étoiles: Dubhe ( D ), Merak ( R ), Phecda ( P ), Megrez ( M ), Alioth ( A ), Mizar ( I ) et Alkaid ( K ). https://chingmath.fr chapExoCorrec/7675 sacados/7675 ABCDEFG chapExoCorrec/7678 sacados/7678 MSRFCPD chapExoCorrec/8188 sacados/8188 EJNSWMAI
Les arêtes représentées sont les déplacements possibles et les nombres inscrits sont les distances exprimées en ˇannée-lumièreı. Les participants doivent trouver le chemin le plus court pour aller de l’étoile Alkaid ( K ) à l’étoile Dubhe ( D ) le plus rapidement possible. Utiliser le tableau ci-dessous pour présenter l’algorithme de Dijkstra appliqué à ce graphe afin de déterminer le plus cours chemin entre ces deux étoiles. K I A M P R D On précisera alors le chemin le plus court et sa distance. 2. Programmation linéaire: méthode du simplexe E.7676 Une entreprise produit des verres de différentes qualités. À cause des problèmes d’approvisionnement, elle surveille l’utilisation des deux élé-ments : la silice, le germanium et l’arsenic. De plus, on a les informations suivantes : Pour construire cent plats en verres, l’entreprise utilise: 3 kg de silice, 1 kg de germanium et 1 kg d’arsenic. Pour construire cent bols en verres, l’entreprise utilise: 1 kg de silice, 2 kg de germanium et 10 kg d’arsenic. L’entreprise dispose de 3 kg de silice, 2 kg de germanium et 9 kg d’arsenic. On notera x et y les nombres respectivement de centaines de plats en verre et de centaines de bols en verres. Chaque plat est vendu 4 e et chaque bol est vendu 3 e . 1 Exprimer les contraintes du problème sous la forme d’un système d’inéquations. Exprimer la fonction donnant le chiffre d’affaires réalisé en centaines d’euros en fonction de x et de y . 2 Dans cette question, on cherche à optimiser le chiffre d’affaires. a Représenter ci-dessous l’ensemble des solutions réalisa-bles. b Par méthode graphique, déterminer la solution max-imisant la valeur de l’expression 4 · x +3 · y . c En déduire le chiffre d’affaires maximal que peut réaliser l’entreprise. https://chingmath.fr KIAMPRD1631541571741419 chapExoCorrec/7676 sacados/7676 x-0,200,20,40,60,811,21,4y-0,20,20,40,60,811,21,4
E.8189 Un bijoutier se lance dans la production ˇ à la chaine ı de deux types de bijoux : La bague ˇ Égypte ı qui nécessite 6 grammes d’or, 4 grammes de platine et 6 grammes d’argent. Le collier ˇ Babylone ı qui nécessite 30 grammes d’or, 5 grammes de platine et 3 grammes d’argent. Le bijoutier dispose dans son atelier de 180 grammes d’or, 45 grammes de platine, 60 grammes d’argent. On notera x et y les nombres respectivement de bagues ˇ Égypte ı et de colliers ˇ Babylone ı confectionnés. Chaque bague sera vendue 17 e et chaque collier 51 e . Aidons le bijoutier à décider du nombre de bagues et de colliers qu’il doit confectionner afin d’optimiser son chiffre d’affaires s’il vend toutes ses productions. 1 Exprimer les contraintes du problème sous la forme d’un système d’inéquations. Exprimer la fonction donnant le chiffre d’affaires réalisé en euros en fonction de x et de y . 2 Dans cette question, on cherche à optimiser le chiffre d’affaires. a Représenter ci-dessous l’ensemble des solutions réalis-ables. b Par méthode graphique, déterminer la solution max-imisant la valeur de l’expression 17 · x +51 · y . c En déduire le chiffre d’affaires maximal que peut réaliser le bijoutier. 3. Algorithme du simplexe E.7677 Une entreprise produit des verres de différentes qualités. À cause des problèmes d’approvisionnement, elle surveille l’utilisation des deux élé-ments : la silice, le germanium et l’arsenic. De plus, on a les informations suivantes : Pour construire cent plats en verres, l’entreprise utilise: 3 kg de silice, 1 kg de germanium et 1 kg d’arsenic. Pour construire cent bols en verres, l’entreprise utilise: 1 kg de silice, 2 kg de germanium et 10 kg d’arsenic. L’entreprise dispose de 3 kg de silice, 2 kg de germanium et 9 kg d’arsenic. On notera x et y les nombres respectivement de centaines de plats en verre et de centaines de bols en verres. Chaque plat est vendu 4 e et chaque bol est vendu 3 e . 1 Exprimer les contraintes du problème sous la forme d’un système d’inéquations. Exprimer la fonction donnant le chiffre d’affaires réalisé en centaines d’euros en fonction de x et de y . 2 À l’aide l’algorithme du simplexe, recherche le chiffre d’affaires maximal sous les contraintes données précédem-ment. 4. TD 5 L4 E.8088 Pour le graphe G ci-dessous : https://chingmath.fr chapExoCorrec/8189 sacados/8189 x-3-2-101234567891011y-3-2-11234567891011 chapExoCorrec/7677 sacados/7677 chapExoCorrec/8088 sacados/8088 1234567
1 Déterminer la matrice M associée au graphe G . 2 Déterminer d + et d − . 3 Le graphe est-il sans circuit? Si oui, le partager en niveaux. 4 Donner alors une nouvelle représentation du graphe. E.8089 Pour le graphe G ci-dessous : 1 Déterminer la matrice M associée au graphe G . 2 Déterminer d + et d − . 3 Le graphe est-il sans circuit? Si oui, partager en niveaux. 4 Donner alors une nouvelle représentation du graphe. E.8090 Tracer le graphe de la matrice d’adjacence suivante : 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 E.8091 Tracer le graphe de la matrice d’adjacence suivante : 0 0 1 1 1 0 0 0 0 1 0 1 0 1 0 0 E.8092 On veut transporter des pro-duits chimiques par le rail. A , B , C , D , E , F , G et H désig-nent huit produits chimiques. Dans le tableau ci-dessous, une croix signifie que les produits ne peuvent pas être entreposés dans le même wagon, car il y aurait risque d’explosion. 1 Construire le graphe où les sommets sont les produits chimiques et où les arêtes représentent les incompatibil-ités de stockage de ces produits entre eux. 2 Écrire la matrice d’adjacence correspondante. 3 On souhaite utiliser un minimum de wagons pour trans-porter l’ensemble de ces produits chimiques. Expliquer en quoi l’algorithme de Welsh-Powell permet de répondre à cette question. 4 Appliquer cet algorithme. 5. TD 6 L4 E.8093 Des étudiants A , B , C , D , E et F doivent passer des examens dans différentes disciplines, chaque examen occupant une demi-journée : Chimie : étudiants A et B . Électronique : étudiants C et D . Informatique : étudiants C , E , F et G . Mathématiques : étudiants A , E , F et H . Physique: étudiants B , F , G et H . On cherche à organiser la session d’examens la plus courte possible. E.8094 Voici le graphe valué qui mod-élise un trafic aérien américain. Quel est le chemin le moins cher pour aller de Miami à Los Angeles? https://chingmath.fr chapExoCorrec/8089 sacados/8089 ABCDEFGH chapExoCorrec/8090 sacados/8090 chapExoCorrec/8091 sacados/8091 chapExoCorrec/8092 sacados/8092 chapExoCorrec/8093 sacados/8093 chapExoCorrec/8094 sacados/8094 San FranciscoLos AngelesDenverChicagoBostonNew YorkAtlantaMiami39$55$99$89$129$69$79$65$99$39$79$99$69$129$
E.8095 Un transporteur veut aller le plus vite possible de Nantes à Brest par la route. Aidez-le à trouver son chemin Les nombres indiqués représentent des temps de trajet en min . E.8278 Le gestionnaire d’un aéroport doit évaluer le nombre minimal de pistes de décollage en fonction du type d’avions. La longueur de la piste de décollage de l’avion qui s’y pose. Pour respecter la réglementation sur les distances de sécurité en fonction de la cadence, certains avions ne peuvent pas se poser sur les mêmes pistes. Le tableau ci-dessous récapitule ces incompatibilités : une croix représente le fait que ces avions ne peuvent décoller de la même piste. A320 A321 B373 A380 A350 B777 A320 × × × × A321 × × × B373 × × × A380 × × A350 × × × × B777 × × Quel est le nombre minimal de pistes de décollage dont l’aéroport doit se doter? E.8279 Voici le graphe valué qui modélise le plan d’un quartier que droit travers un coursier pour livre un colis en temps minimal de l’entrepôt de départ A au point de livraison K . Chaque sommet représente un croisement et chaque arc une rue. La valeur attribuée à l’arc représente le temps de parcours en minutes. Quel est le chemin le plus rapide? 6. TD 7 L4 E.8096 On veut affecter 5 tâches à 5 machines. Les coûts des affectations sont donnés par le tableau suivant : machine 1 machine 2 machine 3 machine 4 machine 5 Tâche 1 15 40 5 20 20 Tâche 2 22 33 9 16 20 Tâche 3 40 6 28 0 26 Tâche 4 8 0 7 25 60 Tâche 5 10 10 60 15 5 Rechercher une affectation conduisant à un coût minimum en utilisant l’algorithme hongrois. https://chingmath.fr chapExoCorrec/8095 sacados/8095 NantesRennesVannesLorientQuimperPontivyCarhaixChateaulinBrest BrestBrestCarhaixCarhaixChateaulinChateaulinLorientLorientNantesNantesPontivyPontivyQuimperQuimperRennesRennesVannesVannes3535506035352550454540757560457545254575757040754570 chapExoCorrec/8278 sacados/8278 chapExoCorrec/8279 sacados/8279 ABCDEFGHIJK123115774211513212 chapExoCorrec/8096 sacados/8096
E.8097 Déterminer par la méthode hongroise une affectation de coût minimal associée à la ma-trice des coûts suivant : 7 2 1 9 4 9 6 9 5 5 8 8 3 1 8 7 9 4 2 2 4 3 7 4 8 E.8098 Résoudre : max: 1 200 · x 1 +1 000 · x 2 sous contrainte : 3 x 1 + 4 x 2 160 6 x 1 + 3 x 2 180 x 1 0 x 2 0 Résoudre ce problème graphiquement puis par l’algorithme du simplexe. E.8280 Dans le cadre de sa politique anti-pollution de son entreprise, un transporteur veut aller de Montpellier à Cahors en consommant le moins d’émissions de particules polluantes possibles : Les nombres indiqués représentent les émissions de particules polluantes sur le trajet. Déterminer le trajet à emprunter par le transporteur. 7. TD 8 L4 E.8099 Un ouvrier fabrique 2 types d’agenda Ag 1 et Ag 2 : Ag1 1 heure de fabrication Coût de fabrication : 3 e Profit : 2 e Ag2 2 heures de fabrication Coût de fabrication : 2 e Profit : 3 e L’ouvrier travaille 8 heures par jour. L’ouvrier peut investir 12 e = jour pour la fabrication de ses agendas. Combien faut-il fabriquer d’agenda de chaque type par jour pour maximiser le profit? E.8100 Un artisan chocolatier décide de confectionner des oeufs en chocolat. En réserves, il lui reste 18 kg de cacao, 8 kg de noisettes et 14 ‘ de lait. Il a deux spécialités: l’oeuf Extra et l’oeuf Sublime. Un oeuf Extra nécessite 1 kg de cacao, 1 kg de noisettes et 2 ‘ de lait. Un oeuf Sublime nécessite 3 kg de cacao, 1 kg de noisettes et 1 ‘ de lait. Il fera un profit de 20 euros en vendant un oeuf Extra, et de 30 euros en vendant un oeuf Sublime. Combien d’oeufs Extra et Sublime doit-il fabriquer pour faire le plus grand bénéfice possible? 8. Coloration d’un graphe https://chingmath.fr chapExoCorrec/8097 sacados/8097 chapExoCorrec/8098 sacados/8098 chapExoCorrec/8280 sacados/8280 13520515513580858055855520530125155959530505035555512535MontpellierMontpellierRodezRodezVillefranche de R.VillefranchedeRouergueFigeacFigeacAlbiAlbiCarcassonneCarcassonneToulouseToulouseMontaubanMontaubanCahorsCahors MontpellierCarcassonneToulouseAlbiMontaubanRodezVillefranchedeRouergueFigeacCahors chapExoCorrec/8099 sacados/8099 chapExoCorrec/8100 sacados/8100 fichierPlus/8100/diapoCorrection.pdf
E.7665 Ci-dessous sont représentés sept rectan-gles blancs : Colorier avec un minimum de couleurs ces sept rectangles. E.7664 Les points de collecte d’un camion d’une société recyclant des ˇ déchets papier ı ainsi que les tra-jets possibles entre ces différents points sont représentés par le graphe ci-dessous : Le dépôt est représenté par le sommet A et les autres sommets représentent les différents points de collecte. Afin de rendre son plan plus lisible, le chauffeur du camion souhaite colorer les sommets du graphe représentant son réseau de manière que deux sommets adjacents n’aient jamais la même couleur. Combien de couleurs au minimum peut-il utiliser? E.7666 Une entreprise de produits cosmé-tique fait réaliser une étude marketing sur une population donnée. L’étude marketing montre que certains produits ne sont ja-mais achetés simultanément. On représente les incompatibil-ités par le graphe suivant, où deux sommets reliés représentent deux produits qui ne sont jamais dans une même commande. Par exemple, les produits A et B , représentés par des som-mets reliés, ne sont jamais dans une même commande. L’entreprise souhaite répartir les produits dans des lots consti-tués de produits ne présentant aucune incompatibilité d’achat. Combien de lots doit-elle prévoir au minimum? Justifier votre réponse à l’aide d’un algorithme et proposer une répartition des produits. E.7667 Déterminer le nombre chromatique » du graphe ci-dessous : https://chingmath.fr sacados/7665 chapExoCorrec/7664 sacados/7664 ABCDEFGH sacados/7666 Extrait Antilles-Guyane Septembre 2013 ABCDEFGH sacados/7667 ABCDEFG
E.7668 Un groupe d’amis organise une ran-donnée dans les Alpes. On a représenté par le graphe ci-dessous les sommets B , C , D , F , T , N par lesquels ils peuvent choisir de passer. Une arête entre deux sommets coïncide avec l’existence d’un chemin en-tre les deux sommets. 1 Recopier et compléter le tableau suivant : Sommets B C D F N T Degré des sommets du graphe 2 Le groupe souhaite associer chaque sommet à une couleur de sorte que les sommets reliés par un chemin n’ont pas la même couleur. On note n le nombre chromatique du graphe. a Montrer que : 4  6 b Proposer un coloriage du graphe permettant de déter-miner son nombre chromatique. E.7669 À l’occasion de la coupe du monde de football 2006 en Allemagne, une agence touristique organ-ise des voyages en car à travers les différentes villes où se joueront les matchs d’une équipe nationale. Pour des raisons de sécurité, les supporters de certaines équipes nationales participant à la coupe du monde de foot-ball en 2006 ne peuvent être logés dans le même hôtel. On donne ci-dessous le graphe d’incompatibilité entre les sup-porters de différentes équipes : par exemple, un supporter de l’équipe A ne peut être logé avec un supporter de l’équipe B 1 Déterminer le nombre chromatique de ce graphe en jus-tifiant la valeur trouvée. 2 Prouver une répartition des supporters par hôtel en util-isant un nombre minimum d’hôtels. E.7673 Une compagnie aérienne propose des vols directs entre certaines villes, notées A , B , C , D , E , F et G . Cela conduit au graphe G suivant, dont les sommets sont les villes et les arêtes représentent les liaisons aériennes : 1 Le graphe G est-il complet? Quel est l’ordre de G ? 2 a Sur les cartes d’embarquement, la compagnie at-tribue à chaque aéroport une couleur, de sorte que deux aéroports liés par un vol direct aient des couleurs différentes. Proposer un coloriage adapté à cette condition. b Que peut-on en déduire sur le nombre chromatique de G ? 3 a Quelle est la nature du sous graphe formé par les sommets A , B , C et D ? b Quel est le nombre minimal de couleurs que la compag-nie doit utiliser pour pouvoir attribuer une couleur à chaque aéroport en respectant les conditions du 2 ? 9. Chaine et cycle eulériens E.6243 On considère le graphe ci-contre : Déterminer une chaîne euléri-enne de ce graphe. https://chingmath.fr sacados/7668 BCFDTN sacados/7669 APCQERG sacados/7673 ABCDEFG chapExoCorrec/6243 sacados/6243 ABCDEF
E.6244 On considère le graphe ci-contre : 1 Justifier que le graphe est complet. 2 Déterminer un cycle eu-lérien. E.6273 On considère le graphe G ci-dessous : 1 a Déterminer en justifiant si le graphe G est complet. b Déterminer en justifiant si le graphe G est connexe. 2 a Donner le degré de chacun des sommets du graphe G . b Déterminer en justifiant si le graphe G admet un cycle eulérien ou une chaîne eulérienne. 3 a Donner la matrice M associée au graphe G (les som-mets seront rangés dans l’ordre alphabétique) . b On donne : M 2 = 4 2 2 1 2 2 2 1 1 2 5 1 3 1 1 1 2 0 2 1 4 2 1 1 1 2 2 1 3 2 4 1 1 0 1 0 2 1 1 1 2 2 0 0 0 2 1 1 1 2 2 0 0 0 2 1 1 0 0 0 3 2 1 1 2 2 1 0 0 2 4 1 1 0 2 0 0 0 1 1 2 Montrer, par le calcul, que le coefficient de la septième ligne et quatrième colonne de la matrice M 3 est égal à 3 . E.6274 On considère le graphe G ci-dessous : 1 Ce graphe admet-il une chaîne eulérienne? Justifier la réponse. Si oui, donner une telle chaîne. 2 Ce graphe admet-il un cycle eulérien? Justifier la réponse. Si oui, donner un tel cycle. 3 Donner la matrice M associée au graphe G . Les sommets seront pris dans l’ordre alphabétique: A , B , C , D , E , F , G . E.6275 Parmi les affirmations ci-dessous, lesquelles sont exactes. Les réponses doivent être justifiées. On considère le graphe G représenté ci-dessous : 1 Le graphe G admet une chaîne eulérienne. 2 Le graphe G admet un cycle eulérien. 3 Le graphe G est complet. 4 Le graphe G le graphe admet un sous-graphe stable d’ordre 4 . 5 Le graphe G n’est pas connexe. https://chingmath.fr chapExoCorrec/6244 sacados/6244 ABCDE chapExoCorrec/6273 sacados/6273 ABCDEFGHI chapExoCorrec/6274 sacados/6274 ABCDEFG chapExoCorrec/6275 sacados/6275 ABCDE
E.6276 On considère un espace de jeu réservé à des enfants. Les enfants peuvent se déplacer sur cinq plates-formes notées A , B , C , D et E . Ces plates-formes sont reliées entre elles par un certain nom-bre de rampes, comme indiqué sur le schéma ci-dessous : On représente cet espace de jeu par le graphe G ci-dessous : Une plate-forme est représentée par un sommet et une rampe est représentée par une arête. 1 Donner un sous-graphe complet d’ordre 4 du graphe G . 2 Ce graphe est-il connexe? Est-il complet? Justifier les réponses. 3 Ce graphe contient-il une chaîne eulérienne? Justifier la réponse. 4 Si on rajoute une arête à ce graphe, quels sommets peut-on alors relier pour que le graphe obtenu contienne un cycle eulérien? Justifier la réponse. E.6291 Soit M la matrice carrée d’ordre 5 : M = 0 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 Construire le graphe associé à M . On appellera A , B , C , D , E les sommets. Ce graphe est-il connexe? Est-il complet? 2 Existe-t-il une chaîne eulérienne? Existe-t-il un cycle eulérien? E.6292 On considère le graphe G ci-dessous : 1 Justifier les affirmations suivantes : a Le graphe G admet au moins une chaîne eulérienne. b La chaîne D − A − B − C − F − B − E − F − A − E n’est pas une chaîne eulérienne de G . 2 Déterminer un sous-graphe complet de G , ayant le plus grand ordre possible. E.6293 L’objet d’étude est le réseau des égouts d’une ville. Ce réseau est modélisé par le graphe ci-dessous : les sommets représentent les stations et les arêtes, les canalisations. Ce graphe admet-il une chaîne eulérienne? E.6294 On considère le graphe non orienté G de sommets A , B , C , D , E dont la matrice est : 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 Trois propositions sont proposées ci-dessous et parmi elles, une seule est exacte. Laquelle ? a Le graphe G comporte 12 arêtes. b Le graphe G admet une chaîne eulérienne. c Le graphe G est complet. https://chingmath.fr chapExoCorrec/6276 sacados/6276 ADCBE ABCDE chapExoCorrec/6291 sacados/6291 chapExoCorrec/6292 sacados/6292 ABCDEF chapExoCorrec/6293 sacados/6293 ABCDEFG chapExoCorrec/6294 sacados/6294
E.6295 On considère le graphe G suivant : 1 Le graphe G est-il connexe? Expliquer la réponse. 2 Le graphe G admet-il des chaînes eulériennes? Si oui, préciser une. 3 Justifier la non-existence d’un cycle eulérien pour le graphe G . Quelle arête peut-on alors ajouter à ce graphe pour obtenir un graphe contenant un cycle eulérien? E.6296 Le graphe ci-dessous représente le plan d’une ville. Le sommet A désigne l’emplacement des services techniques. Les sommets B , C , D , E , F et G désignent les emplacements de jardins publics. Une arête représente l’avenue reliant deux emplacements. On s’intéresse au graphe non pondéré. Répondre sans justification aux quatre questions suivantes : a Ce graphe est-il connexe? b Ce graphe est-il complet? c Ce graphe admet-il une chaîne eulérienne? d Ce graphe admet-il un cycle eulérien? E.6329 On considère le graphe ci-contre : 1 À l’aide d’un tableau, donner les degrés de chaque sommet de ce graphe. 2 Justifier que ce graphe admet une chaîne eulérienne. 3 Justifier que les trois chaînes suivantes ne sont pas des chaînes eulériennes. a B − A − D − E − B − F − A − C − F − D b F − D − A − B − E − D − A − C − D − F c B − E − D − C − A − D − F − B − A 4 Donner une chaîne eulérienne de ce graphe. E.6331 On considère une maison composée de 6 pièces dont le plan est donné ci-dessous : 1 En associant chaque pièce à un sommet, construire le graphe G représentant la maison où les arêtes représen-tent la présence d’une porte permettant de passer d’une pièce à l’autre. 2 Justifier vos réponses : a Le graphe G admet-il une chaîne eulérienne? Si oui, écrire cette chaîne. b Le graphe G admet-il un cycle eulérien? Si oui, écrire ce cycle. E.6338 On a schématisé ci-dessous le plan d’une MJC (Maison de la Jeunesse et de la Culture) par un graphe dont les sommets sont les salles et les arêtes sont les passages (portes, couloirs ou escaliers) entre les salles. On appelle H le hall d’entrée et B le bureau du directeur. En fin de journée, un agent de service fait le tour de la MJC pour récupérer dans chaque salle (bureau du directeur et hall inclus) les objets oubliés par les enfants. 1 Préciser si ce graphe est connexe en justifiant la réponse. 2 Déterminer, en justifiant, si l’agent de service peut passer par toutes les salles en utilisant une fois et une seule chaque passage. 3 On range les sommets par ordre alphabétique. Donner la matrice d’adjacence M associée au graphe. 4 On donne : M 4 = 31 15 26 21 27 18 12 15 12 15 12 18 12 6 26 15 31 18 27 21 12 21 12 18 20 17 18 5 27 18 27 17 34 17 16 18 12 21 18 17 20 5 12 6 12 5 16 5 10 En déduire le nombre de chemins de longueur 4 entre les sommets B et H . https://chingmath.fr chapExoCorrec/6295 sacados/6295 Extrait d'Antilles-Guyane Juin 2009 ABCDEF chapExoCorrec/6296 sacados/6296 ABCDEFG chapExoCorrec/6329 sacados/6329 ABCDEF chapExoCorrec/6331 sacados/6331 ABCDEF chapExoCorrec/6338 sacados/6338 Extrait Liban Mai 2014 ABCDEFH
E.6339 Lors d’une campagne élec-torale, un homme politique doit effectuer une tournée dans les villes A , B , C , D , E , F , G et H , en utilisant le réseau au-toroutier. Le graphe G ci-dessous, représente les différentes villes de la tournée et les tronçons d’autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d’autoroute par une arête) : 1 Déterminer, en justifiant, si le graphe G est : a complet b connexe 2 a Justifier qu’il est possible d’organiser la tournée en passant au moins une fois par chaque ville, tout en empruntant une fois et une seule chaque tronçon d’autoroute. b Citer un trajet de ce type. 3 On appelle M la matrice d’adjacence associée au graphe G (les sommets étant pris dans l’ordre alphabétique) . a Déterminer la matrice M . b On donne la matrice: M 3 = 0 5 3 5 1 1 4 1 5 2 7 2 8 3 3 5 3 7 6 4 9 3 9 10 5 2 4 0 9 2 3 8 1 8 9 9 4 4 10 4 1 3 3 2 4 2 6 6 4 3 9 3 10 6 6 9 1 5 10 8 4 6 9 4 Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant E à H . Préciser ces chemins. 10. Graphe étiqueté E.6390 Pour accéder à sa messagerie, Antoine a choisi un code qui doit être reconnu par le graphe étiqueté suivant, de sommets 1 , 2 , 3 et 4 : Une succession des lettres constitue un code possible si ces let-tres se succèdent sur un chemin du graphe orienté ci-dessus, ne partant du sommet 1 et en sortant au sommet 4 . Les codes SES et SPPCES sont ainsi des codes possibles, con-trairement aux codes SUN et SPEN . 1 Parmi les trois codes suivants, écrire sur votre copie le (ou les) code (s) reconnu (s) par le graphe. SUCCES ; SCENES ; SUSPENS 2 Recopier et compléter la matrice d’adjacence A asso-ciée au graphe. On prendra les sommets dans l’ordre 1 − 2 − 3 − 4 . A = 0 1 0 0 1 2 1 0 : : : : : : : : : : : : : : : : : : : : : : : : 3 Avec une calculatrice, on a calculé: A 4 = 5 12 8 3 12 29 20 8 0 0 1 1 0 0 0 0 En déduire le nombre de codes de 4 lettres reconnus par le graphe. Quels sont ces codes? 11. Algorithme de Dijkstra E.6372 Lors d’une campagne électorale, un homme politique doit effectuer une tournée dans les villes A , B , C , D , E , F , G et H , en utilisant le réseau autoroutier. Le graphe G ci-dessous, représente les différentes villes de la tournée et les tronçons d’autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d’autoroute par une arête) : Des contraintes d’organisation obligent cet homme politique à se rendre dans la ville F après la ville A . Le graphe G indique les longueurs en kilomètre de chaque tronçon d’autoroute. https://chingmath.fr chapExoCorrec/6339 sacados/6339 ABCDEFGH chapExoCorrec/6390 sacados/6390 chapExoCorrec/6372 sacados/6372
Déterminer, en utilisant l’algorithme de Dijkstra, le trajet au-toroutier le plus court pour aller de A à F . Préciser la longueur en kilomètre de ce trajet. E.6373 On considère le graphe G ci-dessous et est indiqué, sur chaque arête, le nombre de sec-ondes nécessaires au parcours de chacune d’elle: Déterminer, à l’aide de l’algorithme de Dijkstra, le chemin permettant de relier le sommet G au sommet D en un temps minimal. Déterminer ce temps minimal, exprimé en seconde. E.6370 On considère le graphe ci-dessous où sont indiquées les durées de parcours pour chacune d’elles. Déterminer la chaîne la plus courte reliant les sommets A et D . E.6351 On considère le graphe ci-dessous : 1 a Construire la matrice M d’adjacence de ce graphe (on considèrera les sommets dans l’ordre alphabétique) . b À l’aide de la calculatrice, déterminer l’expression de la matrice M 3 . c Justifier qu’il existe 5 chaînes de longueur 3 relient le sommet A au sommet F ? Donner ces cinq chaînes. 2 On a ajouté sur ce graphe, les distances de chacune des arêtes. Quelle est la chaîne la plus courte de longueur 3 reliant le sommet A au sommet F ? E.6378 Le directeur de l’entreprise E rend visite à ses fournisseurs, il se rend du fournisseur A au fournisseur H et souhaite effectuer le moins de kilomètres pos-sible. Son assistant dresse le graphe suivant qui schématise les tra-jets, en kilomètres, entre les six villes de la région, notée B , C , D , E , F et G et les deux sites, A et H . Déterminer l’itinéraire le plus court reliant les deux sites A et H et indiquer le nombre de kilomètres à effectuer. Justifier la réponse. https://chingmath.fr ABCDEFGH400600600400350550450300900600200400300 chapExoCorrec/6373 sacados/6373 ABCDEFGHI304570603080503590256035402025 chapExoCorrec/6370 sacados/6370 ABCDEF45746742 chapExoCorrec/6351 sacados/6351 ABCDEFG ABCDEFG4784274417585 chapExoCorrec/6378 sacados/6378 Extrait d'Asie Juin 2013 ABCDEFGH100175158114150956570107821133111249
E.6379 Une partie d’un domaine skiable est représentée par le graphe ci-dessous. Le sommet A représente le haut des pistes de ski et le sommet I en représente le bas. Les sommets B , C , D , E , F , G et H représentent des points de passages. Chacune des arêtes est pondérée par la distance, en centaine de mètres, entre deux sommets. Déterminer, à l’aide de l’algorithme de Dijkstra, la distance minimale permettant de relier le sommet A au sommet I . E.6385 Une région est munie d’un réseau de trains, représenté par le graphe Γ ci-dessous. Les stations sont symbolisées par les sommets A , B , C , D , E , F et G . Chaque arête représente une ligne reliant deux gares. Les temps de parcours (correspondance comprise) en minutes entre chaque sommet ont été rajoutés sur le graphe. 1 Déterminer le plus court chemin en minutes, reliant la gare B à la gare G . 2 Quelle est la longueur en minutes de ce chemin? E.6389 Les points de collecte d’un camion d’une société recyclant des ˇ déchet papier ı ainsi que le temps de tra-jet (en minutes) entre ces différents points, sont représentés par le graphe ci-dessous. Le dépôt est représenté par le som- met A et les autres sommets représentent les différents points de collecte. Le conducteur doit se rendre du dépôt A au point de col-lecte H . Il cherche le chemin qui minimise le temps de trajet. Déterminer ce chemin en expliquant le procédé utilisé, et pré-ciser le temps minimum de parcours obtenu. E.6116 On considère le graphe G ci-dessous où sont indiqués sur chacune des arêtes le temps de parcours, en minutes, pour relier deux sommets de ce graphe. Déterminer, à l’aide de l’algorithme de Dijkstra, le chemin permettant de relier le sommet A au sommet F en un temps minimal. E.6367 On considère le graphe G ci-dessous où sont indiqués sur chacune des arêtes le temps de parcours, en minutes, pour relier deux sommets de ce graphe. Déterminer, à l’aide de l’algorithme de Dijkstra, le chemin permettant de relier le sommet A au sommet F en un temps minimal. 12. Algorithme de Dijkstra présentant des égalités de chemins E.6374 Le graphe ci-dessous représente, dans un aéroport donné, toutes les voies empruntées par les avions au roulage. Ces voies, sur lesquelles circulent les avions avant ou après atterrissage, sont appelées taxiways . Les arêtes du graphe représentent les voies de circulation (les https://chingmath.fr chapExoCorrec/6379 sacados/6379 ABCDEFGHI7162113181581285651218713719 chapExoCorrec/6385 sacados/6385 ABCDEFG4871821102515123110177 chapExoCorrec/6389 sacados/6389 ABCDEFGH3711371143928104712 chapExoCorrec/6116 sacados/6116 ACBDEF155251475101811 chapExoCorrec/6367 sacados/6367 ACBDEF155257510186 chapExoCorrec/6374 sacados/6374
ˇtaxiwaysı) et les sommets du graphe sont les intersections. Dans le graphe ci-dessous, on a indiqué le sens de circulation pour les avions dans les différentes voies ainsi que le temps de parcours pour chacune en minute(s). 1 a Écrire la matrice M associée à ce graphe (ranger les sommets dans l’ordre alphabétique) b Citer tous les chemins de longueur 3 reliant A à T . 2 L’avion qui a atterri en bout de piste en A et doit se rendre le plus rapidement possible au terminal situé au point T . Déterminer l’itinéraire le plus rapide et en donner la durée. E.6368 On considère le graphe ci-dessous : Quel est le chemin le plus court pour relier le sommet B au sommet H ? E.6369 On considère le graphe G suivant : À l’aide de l’algorithme de Dijkstra, déterminer les deux chemins les plus courts reliant les sommets A et F . 13. Annales E.6232 Un parc de loisirs propose à ses visiteurs des parcours d’accrobranches. Les différents parcours sont modélisés par le graphe Γ ci-dessous où les sommets correspondent aux cinq arbres mar-quant leurs extrémités. Chaque parcours est représenté par une arête du graphe et peut être réalisé dans les deux sens. 1 L’organisateur du parc de loisirs souhaite que les visi-teurs puissent, s’ils le souhaitent, réaliser un itinéraire complet d’accrobranches, c’est-à-dire un itinéraire em-pruntant une fois et une seule chaque parcours et en com-mençant cet itinéraire par l’arbre numéro 1 . Justifier que ce souhait est réalisable et proposer un tel itinéraire. 2 On note M la matrice associée au graphe Γ en consid-érant les sommets pris dans l’ordre croissant des numéros d’arbres. a Écrire la matrice M . b On donne, ci-dessous, les matrices M 2 et M 3 . M 2 = 3 2 2 1 1 2 4 1 1 2 2 1 2 1 1 1 1 1 2 2 1 2 1 2 3 ; M 3 = 4 7 3 5 7 7 6 6 6 7 3 6 2 3 5 5 6 3 2 3 7 7 5 3 4 L’organisateur du parc de loisir souhaite organiser des ˇ itinéraires express ı qui débuteront à l’arbre numéro 1 , emprunteront trois parcours d’accrobranches et finiront à l’arbre 4 . Ces itinéraires peuvent éventuelle-ment emprunter plusieurs fois le même parcours. Déterminer, en justifiant votre résultat, le nombre d’ˇ itinéraires expressı réalisables. (On ne demande pas de donner ces différents it-inéraires) 3 Pour terminer ces ˇ itinéraires express ı, on installe un to-boggan géant sur l’arbre 4 . La forme de ce toboggan est modélisée par une fonction f dont la courbe C est donnée ci-dessous dans un repère orthonormé. https://chingmath.fr ABCDEFT4341;50;51230;50;50;540;5 chapExoCorrec/6368 sacados/6368 ABCDEFH24364135324 chapExoCorrec/6369 sacados/6369 ABCDEF52441455241 chapExoCorrec/6232 sacados/6232
Cette courbe passe par les points I , J et K de coordon-nées respectives (2 ; 8 ; 1) , (10 ; 2 ; 5) et (20 ; 0) . La fonction f est définie sur 0 ; 20 par : f ( x ) = ax 2 + bx + c où a , b et c sont trois nombres réels. a Justifier que a , b et c sont solutions du système : 400 a + 20 b + c = 0 100 a + 10 b + c = 2 ; 5 4 a + 2 b + c = 8 ; 1 b Déterminer les matrices X et V pour que le système précédent soir équivalent à: U · X = V où U = 400 20 1 100 10 1 4 2 1 c Déterminer a , b et c . E.6423 Le graphe ci-dessous représente les autoroutes entre les principales villes du Sud de la France : Bordeaux (B), Clermont-Ferrand (C), Lyon (L), Marseille (M), Montpellier (P), Brive (R), Toulouse (T), Valence (V) et Biarritz (Z). 1 Pour cette question, on justifiera chaque réponse a Déterminer l’ordre du graphe. b Déterminer si le graphe est connexe. c Déterminer si le graphe est complet. 2 Un touriste atterrit à l’aéroport de Lyon et loue une voiture. Déterminer, en justifiant, s’il pourra visiter toutes les villes en empruntant une et une seule fois chaque au-toroute. 3 Il décide finalement d’aller seulement de Lyon à Biarritz. On note N la matrice associée au graphe, les sommets étant rangés dans l’ordre alphabétique: B , C , L , M , P , R , T , V , Z . Voici les matrices N et N 3 : N = 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 N 3 = 4 2 1 1 3 6 6 1 5 2 0 5 2 8 6 1 1 3 1 5 0 2 1 0 3 5 0 1 2 2 2 5 2 1 4 1 3 8 1 5 2 1 8 7 1 6 6 0 2 1 2 8 3 2 6 1 3 1 8 8 4 1 6 1 1 5 4 7 3 1 2 1 5 3 0 1 1 2 6 1 2 a En détaillant le calcul, déterminer le coefficient de la troisième ligne et dernière colonne de la matrice N 4 . b En donner une interprétation. 4 Sur les arêtes du graphe sont maintenant indiqués les prix des péages en euro. https://chingmath.fr 02468101214161820246810IJK chapExoCorrec/6423 sacados/6423 Liban Mai 2013 ZBTRCPLVM
a À l’aide de l’algorithme de Dijkstra, déterminer le chemin que doit prendre le touriste pour minimiser le coût des péages de Lyon à Biarritz. b Déterminer le coût, en euro, de ce trajet. E.6402 Dans le jeu ˇ Save the princess ı, l’objectif est d’aller délivrer une princesse tout en récoltant des trésors situés dans les couloirs du château. Le plan du château est représenté par le graphe pondéré ci-dessous. Les sommets de ce graphe représentent les salles et les arêtes représentent les couloirs reliant les salles entre elles. Partie A 1 Le joueur se trouve dans la salle A . Il décide de visiter chacun des couloirs afin de trouver le plus de trésors pos- sibles. Peut-il trouver un trajet lui permettant de passer par tous les couloirs une et une seule fois? Justifier la réponse. 2 Dans chaque couloir se trouve un certain nombre de mon-stres. Les étiquettes du graphe pondéré donnent le nom-bre de monstres présents dans les couloirs. Le joueur souhaite, en partant de A , rejoindre la princesse enfermée dans la salle G . Déterminer le chemin qu’il doit prendre pour délivrer la princesse en combat-tant le moins de monstres possible. Combien de monstres aurait-il alors à affronter? Partie B Pour un joueur régulier, on estime que : s’il gagne une partie, la probabilité qu’il gagne la partie suivante est 0 ; 7 ; s’il perd une partie, la probabilité qu’il perde la partie suivante est 0 ; 6 . On note P n = u n v n l’état probabiliste lors de la n -ième partie où u n désigne la probabilité que la partie soit gagnée et v n celle que la partie soit perdue. 1 Traduire les données de l’énoncé par un graphe proba-biliste. On nommera les sommets U (pour la partie gag-née) et V (pour la partie perdue) . 2 En déduire la matrice de transition en considérant les sommets dans l’ordre U , V . 3 On suppose la première partie perdue, l’état probabiliste initial est donc P 1 = 0 1 . Montrer que la probabilité que le joueur gagne la 3 e par-tie est 0 ; 52 . 4 Déterminer la probabilité que le joueur gagne la 15 e par-tie. Arrondir le résultat au centième. 14. Exercices non-classés E.6115 On considère le graphe G ci-dessous : 1 a Déterminer en justifiant si le graphe G est complet. b Déterminer en justifiant si le graphe G est connexe. 2 a Donner le degré de chacun des sommets du graphe G . b Déterminer en justifiant si le graphe G admet un cycle eulérien ou une chaîne eulérienne. 3 On note M la matrice associée au graphe G (les sommets seront rangés dans l’ordre alphabétique) . On donne les deux informations suivantes : M = 0 1 1 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 https://chingmath.fr ZBTRCPLVM4;4019;6017;5011;5014;6019;6011;508;6010;7016;209;407;1015;70 chapExoCorrec/6402 sacados/6402 Extrait d'Antilles-Guyane Septembre 2014 ABCDEFG573112141414819 chapExoCorrec/6115 sacados/6115 ABCDEFGHI
M 2 = 4 2 2 1 2 2 2 1 1 2 5 1 3 1 1 1 2 0 2 1 4 2 1 1 1 2 2 1 3 2 4 1 1 0 1 0 2 1 1 1 2 2 0 0 0 2 1 1 1 2 2 0 0 0 2 1 1 0 0 0 3 2 1 1 2 2 1 0 0 2 4 1 1 0 2 0 0 0 1 1 2 Déterminer, par le calcul, le coefficient de la septième ligne et quatrième colonne de la matrice M 3 https://chingmath.fr